牛客国庆集训派对Day3 I Metropolis(多源多汇最短路)

本文主要是介绍牛客国庆集训派对Day3 I Metropolis(多源多汇最短路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Metropolis

题意： $p$ 个点 $m$ 条无向边，对于这 $p$ 个点，问距离其它点最近的距离。

题解：首先，如果我们考虑最暴力的方法， $p$ 次单源最短路。但是 $p$ 的大小有 $2 e 5$ ，明显是不可能了。那就考虑多源最短路吧。将这 $p$ 个点都加入队列作为源点。对于每一个节点，我们记录它是由哪一个源点扩展出来的。当从一个源点 $i$ ，扩展到另一个源点 $j$ 扩展出来的一个节点 $u$ 时，那么 $d i s (i, j) = m i n (d i s (i, j), d i s [u] + d i s [v] + w)$

就不需要再继续扩展了。具体看代码叭～

代码

#include<bits/stdc++.h>typedef long long LL;
#define P pair<LL,LL>
using namespace std;
const int N = 2e5+10;
const LL inf = 1e17;
int n,m,p,metrp[N],from[N];struct node{LL v,w;
};
LL dis[N],ans[N];
vector<node> e[N];
priority_queue<P, vector<P>, greater<P> > pq;
void dijkstra()
{memset(dis,0x3f,sizeof dis);for(int i = 0; i < p; ++i)pq.push(P(dis[metrp[i]] = 0, metrp[i]));while(!pq.empty()){P cur = pq.top();pq.pop();LL cost = cur.first;LL u = cur.second;if(dis[u] < cost) continue;int len = e[u].size();for(int i = 0; i < len; ++i){LL v = e[u][i].v;LL w = e[u][i].w;if(dis[u] + w < dis[v]){dis[v] = dis[u] + w;from[v] = from[u];pq.push(P(dis[v],v));}else if(from[u] != from[v]){ans[from[u]] = min(ans[from[u]],dis[u] + dis[v] + w);ans[from[v]] = min(ans[from[v]],dis[u] + dis[v] + w);}}}
}void solve()
{dijkstra();for(int i = 0; i < p; ++i)printf("%lld%c",ans[metrp[i]],i == p - 1 ? '\n' : ' ');
}int main()
{
#ifndef ONLINE_JUDGEfreopen("input.in","r",stdin);
#endifcin>>n>>m>>p;int u,v,w;for(int i = 0; i < p; ++i){cin>>metrp[i];ans[metrp[i]] = inf;from[metrp[i]] = metrp[i];}for(int i = 0; i < m; ++i){cin>>u>>v>>w;e[u].push_back({v,w});e[v].push_back({u,w});}solve();return 0;
}