CF1163F Indecisive Taxi Fee 题解

在改边权之后，可以将所有路径分为经过修改的边和不经过修改的边两种。经过修改的边的所有路径的最小值是容易计算的。具体来说，设修改的边为 $(u,v)$，修改后的权值为 $w$，则预先从 $1$ 和 $n$ 分别跑一遍最短路，假设求出的数组分别为 $d_1$ 和 $d_n$，然后答案就是 $\min\{d_{1,u}+w+d_{n,v},d_{1,v}+w+d_{n,u}\}$。

因此只需要考虑不经过修改的边如何做，转化为删 1 条边。

首先肯定要放到最短路树上考虑。如果断边不在所有 $1-n$ 的最短路的交上则直接取最短路；否则一定要经过一条不在交上的边。而两条这样的边显然没用，提示了这样一个做法：以 $1$ 和 $n$ 为根各任取一棵最短路树，分别设为 $T_1$ 和 $T_n$；如果断边不同时在两棵树的 $1-n$ 的路径上则直接返回原图最短路；否则答案一定是先在 $T_1$ 上走到 $u$，然后经过一条不同时在两条路径上的边到 $v$，然后再在 $T_n$ 上走到 $n$。然后暴力枚举这条边是什么。

尝试优化。考虑到这条边的起点所处的点集是整个树断掉一条边之后仍和根连通的部分，即挖去一棵子树；终点同理。dfs 序处理这类问题很轻松，因此在两棵最短路树上均搜出一个 dfs 序，分别设为 $x_1$ 和 $x_n$。对于所有不同时在两条最短路上的边 $(u,v,w)$，于二维平面上添加两点：位于 $(x_{1,u},x_{n,v})$ 的权值为 $d_{1,u}+w+d_{n,v}$ 的点，和位于 $(x_{1,v},x_{n,u})$ 的权值为 $d_{1,v}+w+d_{n,u}$ 的点。

然后就可以用矩形求 min 来求出最小值了。一般的矩形求 min 不好做，但是这题中是 4 个矩形，且两维均要么是前缀要么是后缀。因此对于所有点，建两棵主席树（一个前缀的一个后缀的），然后分别查询就可以了。

然后就做完了，时间复杂度 $O(m\log m+m\log n)$，空间复杂度 $O(m\log n)$。

但是直接硬上这个做法会爆空间，因此离线下来，分别对于前缀主席树和后缀主席树跑一遍所有询问。这样同一时间只需要维护一棵主席树，空间直接减半，就可以通过了。

const int N = 200005;
const long long INF = 0x3f3f3f3f3f3f3f3f;
struct Edge {
	int to, nxt;
	long long len;
	Edge() {
		nxt = -1;
	}
};
Edge e[N << 1];
int n, hd[N], pnt, m, q, dfn[2][N], pst[2][N], _time, prever[N], sufver[N];
long long dis[2][N], ans[N], qt[N], qx[N];
bool tr[2][N << 1], vis[N], onRoute[2][N << 1];
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > que;
vector <pair <int, long long> > adj[N];

#define Minv(p) (p ? p->mnv : INF)
#define Lc(p) (p ? p->l : NULL)
#define Rc(p) (p ? p->r : NULL)
struct Node {
	long long mnv;
	Node *l, *r;
	inline void Update() {
		mnv = min(Minv(l), Minv(r));
	}
	inline Node() {
		mnv = INF;
		l = r = NULL;
	}
};
Node nd[N * 50];
int top;
struct Segtree {
	Node *_root[N << 1];
	inline void Modify(Node *&p1, Node *p2, int pl, int pr, int idx, long long val) {
		p1 = &nd[++top];
		if (p2) nd[top] = *p2;
		else nd[top] = Node();
		if (pl == pr) {
			p1->mnv = min(p1->mnv, val);
			return;
		}
		int mid = pl + pr >> 1;
		if (mid >= idx) Modify(p1->l, Lc(p2), pl, mid, idx, val);
		else Modify(p1->r, Rc(p2), mid + 1, pr, idx, val);
		p1->Update();
	}
	inline long long Query(Node *p, int pl, int pr, int l, int r) {
		if (l > r) return INF;
		if (pl == l && pr == r) return Minv(p);
		int mid = pl + pr >> 1;
		if (mid >= r) return Query(Lc(p), pl, mid, l, r);
		else if (mid + 1 <= l) return Query(Rc(p), mid + 1, pr, l, r);
		else return min(Query(Lc(p), pl, mid, l, mid), Query(Rc(p), mid + 1, pr, mid + 1, r));
	}
};
Segtree sgt[2];

inline void AddEdge(int u, int v, long long w) {
	e[++pnt].to = v;
	e[pnt].len = w;
	e[pnt].nxt = hd[u];
	hd[u] = pnt;
}

inline void Read() {
	n = qread(); m = qread(); q = qread();
	for (int i = 1;i <= m;i++) {
		int u = qread(), v = qread(), w = qread();
		AddEdge(u, v, w);
		AddEdge(v, u, w);
	}
	for (int i = 1;i <= q;i++) {
		qt[i] = qread(); qx[i] = qread();
	}
}

inline void Dijkstra(int x) {
	memset(dis[x], 0x3f, sizeof(dis[x]));
	if (x) que.push(make_pair(dis[x][n] = 0, n));
	else que.push(make_pair(dis[x][1] = 0, 1));
	while (!que.empty()) {
		int u = que.top().second;
		if (dis[x][u] < que.top().first) {
			que.pop();
			continue;
		}
		que.pop();
		for (int i = hd[u];~i;i = e[i].nxt) {
			if (dis[x][e[i].to] > dis[x][u] + e[i].len) {
				dis[x][e[i].to] = dis[x][u] + e[i].len;
				que.push(make_pair(dis[x][e[i].to], e[i].to));
			}
		}
	}
	memset(vis, 0, sizeof(vis));
	for (int i = 1;i <= n;i++) {
		for (int j = hd[i];~j;j = e[j].nxt) {
			if (dis[x][e[j].to] == dis[x][i] + e[j].len && !vis[e[j].to]) {
				tr[x][j] = 1;
				vis[e[j].to] = 1;
			} 
		}
	}
}

inline bool Dfs(int x, int u) {
	dfn[x][u] = ++_time;
	bool flag = 0;
	if (x == 0 && u == n) flag = 1;
	if (x == 1 && u == 1) flag = 1;
	for (int i = hd[u];~i;i = e[i].nxt) {
		if (tr[x][i]) {
			bool res = Dfs(x, e[i].to);
			onRoute[x][i] = res;
			flag |= res;
		}
	}
	pst[x][u] = _time;
	return flag;
}

inline void Prefix() {
	for (int i = 1;i <= pnt;i += 2) {
		int u = e[i].to, v = e[i + 1].to;
		if ((onRoute[0][i] && onRoute[1][i + 1]) || (onRoute[0][i + 1] && onRoute[1][i])) continue;
		int w = e[i].len;
		adj[dfn[0][u]].push_back(make_pair(dfn[1][v], dis[0][u] + w + dis[1][v]));
		adj[dfn[0][v]].push_back(make_pair(dfn[1][u], dis[0][v] + w + dis[1][u]));
	}
	
}

inline void BuildPre() {
	for (int i = 1;i <= n;i++) {
		int siz = adj[i].size();
		prever[i] = prever[i - 1];
		for (int j = 0;j < siz;j++) {
			sgt[0].Modify(sgt[0]._root[prever[i] + 1], sgt[0]._root[prever[i]], 1, n, adj[i][j].first, adj[i][j].second);
			prever[i]++;
		}
	}
}

inline void BuildSuf() {
	for (int i = n;i >= 1;i--) {
		int siz = adj[i].size();
		sufver[i] = sufver[i + 1];
		for (int j = 0;j < siz;j++) {
			sgt[1].Modify(sgt[1]._root[sufver[i] + 1], sgt[1]._root[sufver[i]], 1, n, adj[i][j].first, adj[i][j].second);
			sufver[i]++;
		}
	}
}

inline void Solve() {
	BuildPre();
	for (int i = 1;i <= q;i++) {
		int t = 2 * qt[i] - 1, x = qx[i], u = e[t].to, v = e[t + 1].to;
		if (!((onRoute[0][t] && onRoute[1][t + 1]) || (onRoute[1][t] && onRoute[0][t + 1]))) {
			ans[i] = min(dis[0][n], min(dis[0][u] + x + dis[1][v], dis[1][u] + x + dis[0][v]));
			continue;
		}
		if (dis[0][u] > dis[0][v]) swap(u, v);
		ans[i] = min(dis[0][u] + x + dis[1][v], dis[1][u] + x + dis[0][v]);
		ans[i] = min(ans[i], sgt[0].Query(sgt[0]._root[prever[dfn[0][v] - 1]], 1, n, 1, dfn[1][u] - 1));
		ans[i] = min(ans[i], sgt[0].Query(sgt[0]._root[prever[dfn[0][v] - 1]], 1, n, pst[1][u] + 1, n));
	}
	top = 0;
	BuildSuf();
	for (int i = 1;i <= q;i++) {
		int t = 2 * qt[i] - 1, x = qx[i], u = e[t].to, v = e[t + 1].to;
		if (!((onRoute[0][t] && onRoute[1][t + 1]) || (onRoute[1][t] && onRoute[0][t + 1]))) continue;
		if (dis[0][u] > dis[0][v]) swap(u, v);
		ans[i] = min(ans[i], sgt[1].Query(sgt[1]._root[sufver[pst[0][v] + 1]], 1, n, 1, dfn[1][u] - 1));
		ans[i] = min(ans[i], sgt[1].Query(sgt[1]._root[sufver[pst[0][v] + 1]], 1, n, pst[1][u] + 1, n));
	}
	for (int i = 1;i <= q;i++) cout << ans[i] << '\n';
}

int main() {
	std::ios::sync_with_stdio(0);
	memset(hd, -1, sizeof(hd));
	Read();
	Dijkstra(0); Dijkstra(1);
	_time = 0; Dfs(0, 1); _time = 0; Dfs(1, n);
	Prefix();
	Solve();
	return 0;
}