在线网站制作系统源码,传奇免费网站建设,中国保险行业协会网站,jsp网站开发期末大作业其实再次看这题的时候。想法就是和强连通分量有关#xff0c;我们很容易发现#xff0c;题目中所说的双向边#xff0c;就构成了一个强连通分量#xff0c;而所谓的单向边#xff0c;则相当于把强连通分量进行缩点#xff0c;然后整个图成为了一个DAG#xff0c;众所周知…
其实再次看这题的时候。想法就是和强连通分量有关我们很容易发现题目中所说的双向边就构成了一个强连通分量而所谓的单向边则相当于把强连通分量进行缩点然后整个图成为了一个DAG众所周知对于DAG,我们可以在O(n)的时间复杂度内处理很多东西比如最短路最长链等。而对于这题我们并不需要求出其强连通分量我们先只建出包含双向边的图由此整个图会分成若干个连通块我们运用dfs去搜出每个连通块即可对于每个连通块我们可以使用dijk去求出其内部的最短路然后对于外部我们运用拓扑排序进行更新即可。
#include bits/stdc.husing namespace std;
const int N 1e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
// const int maxv 4e6 5;
// #define endl \nint n,r,p,s;vectorpll e[N];void add(int u,int v,int w)
{e[u].push_back({v,w});
}int st[N];
int bel[N];
int tot;
vectorint vec[N];
void dfs(int x)
{st[x]1;bel[x]tot;vec[tot].push_back(x);for(auto [u,w] :e[x]){if(!st[u]){dfs(u);}}
}
int dr[N];
queueint q;
int vis[N],d[N];void dijk(int x)
{priority_queuepll,vectorpll,greaterpll p;for(auto t: vec[x]){p.push({d[t],t});}while(!p.empty()){auto [dis,u]p.top();p.pop();if(vis[u]) continue;vis[u]1;for(auto [v,w] :e[u]){if(d[v]d[u]w){d[v]d[u]w;if(bel[v]x){p.push({d[v],v});}}if(bel[v]!x){//coutbel[v] ;if(dr[bel[v]]0) dr[bel[v]]--;if(dr[bel[v]]0) q.push(bel[v]);}}}
}void solve()
{cinnrps;for(int i1;ir;i){int a,b,c;cinabc;add(a,b,c),add(b,a,c);}for(int i1;in;i){if(!st[i]) {tot;dfs(i);}}for(int i1;ip;i){int a,b,c;cinabc;add(a,b,c);dr[bel[b]];}for(int i1;itot;i){// for(auto x: vec[i]) coutx ;if(!dr[i]) q.push(i);//coutendl;}memset(d,0x3f,sizeof d);d[s]0;while(!q.empty()){auto tq.front();q.pop();dijk(t);}for(int i1;in;i){// coutd[i] ;if(d[i]0x3f3f3f3f/2) coutNO PATHendl;else coutd[i]endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--){solve();}system(pause);return 0;
}
