道路与航线

一道类似缩点的好题，先按道路缩点 然后将缩点以后的图按照航线做DAG

在DAG上先跑topsort 在每一个团内部跑dijkstra，同时更新top点 很有意思的一道题目

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

int n,m1,m2,st;

int e[N],ne[N],w[N],h[N],idx;
void add(int a,int b,int c){
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}


int din[N];
int id[N];
vector<int>block[N];
bool df[N];
int cnt;
int dist[N];
bool vis[N];

void dfs(int u,int ids){
df[u] = true;
id[u] = ids;
block[ids].push_back(u);

for(int i=h[u];~i;i=ne[i]){
int j = e[i];
if(!df[j])dfs(j,ids);
} 
}
queue<int>q;
void dijkstra(int ids)
{

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>heap;
for(auto &t:block[ids])heap.push({dist[t],t});


while(heap.size()){

auto t = heap.top();heap.pop();

int ver = t.second,distance = t.first;

if(vis[ver])continue;
vis[ver] = true;

for(int i=h[ver];~i;i=ne[i]){
int j = e[i];
//cout<<ver<<" "<<" "<<j<<"\n";

if(dist[j]>distance+w[i]){
dist[j] = dist[ver]+w[i];
if(id[j]==id[ver]){
heap.push({dist[j],j});
}
}
if(id[j]!=id[ver]&&(--din[id[j]]==0))q.push(id[j]);
}


}

}

void topsort()
{

for(int i=1;i<=cnt;++i)
 if(!din[i]){q.push(i);}
memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis); 
dist[st] = 0;
while(q.size()){

auto t = q.front();
q.pop();
//cout<<t<<"??\n";
dijkstra(t);

}


}

void solve()
{
cin>>n>>m1>>m2>>st;
memset(h,-1,sizeof h);
for(int i=1;i<=m1;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(!df[i])dfs(i,++cnt);


for(int i=1;i<=m2;i++){
int a,b,c;cin>>a>>b>>c;
add(a,b,c);
din[id[b]]++;
}

topsort();


for(int i=1;i<=n;i++)
 if(dist[i]>0x3f3f3f3f/2)cout<<"NO PATH\n";
 else cout<<dist[i]<<"\n";



}

signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
//cin>>_;
_ = 1;
while(_--)solve();
return 0;
}

原文地址：https://blog.csdn.net/m0_60921016/article/details/136988663

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！