G - Road Blocked 2

G - Road Blocked 2

思路

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

所以就可以用最短路加tarjan解决这道题了

怎么判断一条边是否可以构成最短路呢，比如求$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;}
}