[Luogu p8063] shortest paths (graph theory)

Shortest paths

Topic link ：luogu P8063

The main idea of the topic

Here's an undirected graph , Then give you the shortest path , Then for each edge on the shortest path, ask what is the shortest path of the graph after you delete it , If there is no path, output -1.

Ideas

（ Look at the question next to me , I can't make myself numb ）
（ It depends on our wyc A great god ）

Consider how to do , That emotional thinker is the most short-circuit is gone. Find a slightly less bad one to sew .

Then how to sew , First of all, how do we go , For each point, it is to walk the shortest path tree to get .
Then the two sides are sewn up, so you have to run from the beginning to the end .

Then you consider deleting an edge , Two trees will drop a subtree respectively .
Then you think about the rest , There are two situations ：
One is that they intersect , It can be directly connected by these points .
The other is to connect by the side （ Then note that it can't be the edge you deleted ）, Then you can see whether you can be in one of the two sets .

Then you can $O(n^2+nm)$ Ask for the answer .

Code

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

const int N = 2050;
const int M = 1e5 + 100;
struct node {
    
	int x, y, z;
}a[M];
int n, m, S, T, w[N][N], id[N][N], wow[N];
int dis[N], sid[N], faS[N], faT[N], na, nb;
vector <int> g[N], va[N], Gs[N], Gt[N];
bool in[N], goS[N], goT[N];
priority_queue <pair<int, int> > q;

void Dij(int S, int *f, int *fa) {
    
	memset(in, 0, sizeof(in));
	while (!q.empty()) q.pop();
	q.push(make_pair(-0, S)); f[S] = 0;
	while (!q.empty()) {
    
		int now = q.top().second; q.pop();
		if (in[now]) continue; in[now] = 1;
		for (int i = 0; i < g[now].size(); i++) {
     int x = g[now][i], val = va[now][i];
			if (f[x] > f[now] + val) {
    
				f[x] = f[now] + val; q.push(make_pair(-f[x], x)); fa[x] = now;
			}
		}
	}
}

void Init() {
    
	memset(dis, 0x7f, sizeof(dis)); memset(sid, 0x7f, sizeof(sid));
	Dij(S, dis, faS); Dij(T, sid, faT);
	for (int i = 1; i <= n; i++) if (i != S) Gs[faS[i]].push_back(i);
	for (int i = 1; i <= n; i++) if (i != T) Gt[faT[i]].push_back(i);
}

bool check(int x, int y) {
    
	if (x == na && y == nb) return 0;
	if (x == nb && y == na) return 0;
	return 1;
}

int clac() {
    
	memset(goS, 0, sizeof(goS)); memset(goT, 0, sizeof(goT));
	queue <int> q;
	q.push(S);
	while (!q.empty()) {
    
		int now = q.front(); q.pop();
		goS[now] = 1;
		for (int i = 0; i < Gs[now].size(); i++) {
     int x = Gs[now][i];
			if (check(now, x)) q.push(x);
		}
	}
	q.push(T);
	while (!q.empty()) {
    
		int now = q.front(); q.pop();
		goT[now] = 1;
		for (int i = 0; i < Gt[now].size(); i++) {
     int x = Gt[now][i];
			if (check(now, x)) q.push(x);
		}
	}
	
	int ans = 2e9;
	for (int i = 1; i <= n; i++) if (goS[i] && goT[i]) ans = min(ans, dis[i] + sid[i]);
	for (int i = 1; i <= m; i++) {
    
		if (!check(a[i].x, a[i].y)) continue;
		if (goS[a[i].x] && goT[a[i].y]) ans = min(ans, dis[a[i].x] + a[i].z + sid[a[i].y]);
		if (goS[a[i].y] && goT[a[i].x]) ans = min(ans, dis[a[i].y] + a[i].z + sid[a[i].x]);
	}
	return (ans == 2e9) ? -1 : ans;
}

int main() {
    
	scanf("%d %d %d %d", &n, &m, &S, &T);
	for (int i = 1; i <= m; i++) {
    
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
		w[a[i].x][a[i].y] = w[a[i].y][a[i].x] = a[i].z;
		id[a[i].x][a[i].y] = id[a[i].y][a[i].x] = i;
		g[a[i].x].push_back(a[i].y); g[a[i].y].push_back(a[i].x);
		va[a[i].x].push_back(a[i].z); va[a[i].y].push_back(a[i].z);
	}
	scanf("%d", &wow[0]); for (int i = 1; i <= wow[0]; i++) scanf("%d", &wow[i]);
	
	Init();
	
	for (int i = 2; i <= wow[0]; i++) {
    
		na = wow[i - 1]; nb = wow[i];
		printf("%d\n", clac());
	}
	
	return 0;
}