山东省南水北调建设管理局网站,数据库网站模板,上海高端模板建站,做网站什么配置够用G - Road Blocked 2
思路
只有当一条边是从 1 1 1到 n n n的所有最短路构成的图的桥时#xff0c;去掉这条边#xff0c;最短路才会变大
所以就可以用最短路加tarjan解决这道题了
怎么判断一条边是否可以构成最短路呢#xff0c;比如求 1 1 1到 n n n的最短路#xff0…G - Road Blocked 2
思路
只有当一条边是从 1 1 1到 n n n的所有最短路构成的图的桥时去掉这条边最短路才会变大
所以就可以用最短路加tarjan解决这道题了
怎么判断一条边是否可以构成最短路呢比如求 1 1 1到 n n n的最短路分别求出dist1(源点为1)和distn(源点为n)当一条边(端点分别为a,b边长为w)包含再最短路之中时它满足如下条件 dist1[n]dist1[a]wdistn[b]||dist1[n]distn[a]wdist1[b]当然还有其它方法我写的代码就是其他方法只是上面的方法更简单罢了
代码
struct Edge{int a,b,c;
};void solve() {int n,m;cinnm;vectorvectorpii g(n1);vectorEdge es(m1);for(int i1;im;i){int a,b,c;cinabc;es[i]{a,b,c};g[a].push_back({b,i}),g[b].push_back({a,i});}vectorbool st(n1);vectorll dist(n1,1ll60);priority_queuepll,vectorpll,greaterpll q;dist[1]0;q.push({dist[1],1});vectorvectorpii pas(n1);while(q.size()){auto [dis,ver]q.top();q.pop();if(st[ver]) continue;st[ver]true;for(auto [y,id]:g[ver]){int wes[id].c;if(dist[y]disw){pas[y].clear();pas[y].push_back({ver,id});dist[y]disw;q.push({dist[y],y}); }else if(dist[y]disw){pas[y].push_back({ver,id});}}}vectorbool st1(n1);vectorvectorpii fg(n1);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);vectorint dfn(n1),low(n1);vectorbool fst(m1);int timestamp0;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 i1;im;i){cout(fst[i]?Yes:No)endl;}
}
