abc375_G

G - Road Blocked 2

思路

只有当一条边是从\(1\)到\(n\)的所有最短路构成的图的桥时，去掉这条边，最短路才会变大

怎么判断一条边是否可以构成最短路呢，比如求\(1\)到\(n\)的最短路，分别求出dist1(源点为1)和distn(源点为n)，当一条边(端点分别为a,b，边长为w)包含再最短路之中时，它满足如下条件

    dist1[n]=dist1[a]+w+distn[b]||dist1[n]=distn[a]+w+dist1[b]

当然还有其它方法，我写的代码就是其他方法，只是上面的方法更简单罢了

代码

struct Edge{
	int a,b,c;
};

void solve() {
	int n,m;
	cin>>n>>m;
	vector<vector<pii>> g(n+1);
	vector<Edge> es(m+1);
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		es[i]={a,b,c};
		g[a].push_back({b,i}),g[b].push_back({a,i});
	}
	vector<bool> st(n+1);
	vector<ll> dist(n+1,1ll<<60);
	priority_queue<pll,vector<pll>,greater<pll>> q;
	dist[1]=0;
	q.push({dist[1],1});

	vector<vector<pii>> pas(n+1);

	while(q.size()){
		auto [dis,ver]=q.top();
		q.pop();
		if(st[ver]) continue;
		st[ver]=true;
		for(auto [y,id]:g[ver]){
			int w=es[id].c;
			if(dist[y]>dis+w){
				pas[y].clear();
				pas[y].push_back({ver,id});
				dist[y]=dis+w;
				q.push({dist[y],y}); 
			}
			else if(dist[y]==dis+w){
				pas[y].push_back({ver,id});
			}
		}
	}
	vector<bool> st1(n+1);
	vector<vector<pii>> fg(n+1);
	auto dfs=[&](auto && self,int u)->void{
		if(st1[u]) return;
		st1[u]=true;
		for(auto [ver,id]:pas[u]){
			fg[u].push_back({ver,id}),fg[ver].push_back({u,id});
			self(self,ver);
		}
	};
	dfs(dfs,n);
	vector<int> dfn(n+1),low(n+1);
	vector<bool> fst(m+1);
	int timestamp=0;
	auto tarjan=[&](auto && self,int u,int fa)->void{
		dfn[u]=low[u]=++timestamp;
		for(auto [y,id]:fg[u]){
			if(!dfn[y]){
				self(self,y,u);
				low[u]=min(low[u],low[y]);
				if(low[y]>dfn[u]){
					fst[id]=true;
				}
			}
			else if(y!=fa){
				low[u]=min(low[u],dfn[y]);
			}
		}
	};
	tarjan(tarjan,1,0);
	for(int i=1;i<=m;i++){
		cout<<(fst[i]?"Yes":"No")<<endl;
	}
}