算法进阶指南图论 道路与航线

进阶指南图论 道路与航线"/>

算法进阶指南图论 道路与航线

其实再次看这题的时候。想法就是和强连通分量有关，我们很容易发现，题目中所说的双向边，就构成了一个强连通分量，而所谓的单向边，则相当于把强连通分量进行缩点，然后整个图成为了一个DAG，众所周知，对于DAG,我们可以在O(n)的时间复杂度内处理很多东西，比如最短路，最长链等。而对于这题，我们并不需要求出其强连通分量，我们先只建出包含双向边的图，由此，整个图会分成若干个连通块，我们运用dfs去搜出每个连通块即可，对于每个连通块，我们可以使用dijk去求出其内部的最短路，然后对于外部，我们运用拓扑排序进行更新即可。

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
// #define endl "\n"int n,r,p,s;vector<pll> e[N];void add(int u,int v,int w)
{e[u].push_back({v,w});
}int st[N];
int bel[N];
int tot;
vector<int> 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];
queue<int> q;
int vis[N],d[N];void dijk(int x)
{priority_queue<pll,vector<pll>,greater<pll> > 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){//cout<<bel[v]<<" ";if(dr[bel[v]]>0) dr[bel[v]]--;if(dr[bel[v]]==0) q.push(bel[v]);}}}
}void solve()
{cin>>n>>r>>p>>s;for(int i=1;i<=r;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}for(int i=1;i<=n;i++){if(!st[i]) {tot++;dfs(i);}}for(int i=1;i<=p;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);dr[bel[b]]++;}for(int i=1;i<=tot;i++){// for(auto x: vec[i]) cout<<x<<" ";if(!dr[i]) q.push(i);//cout<<endl;}memset(d,0x3f,sizeof d);d[s]=0;while(!q.empty()){auto t=q.front();q.pop();dijk(t);}for(int i=1;i<=n;i++){// cout<<d[i]<<" ";if(d[i]>0x3f3f3f3f/2) cout<<"NO PATH"<<endl;else cout<<d[i]<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}