题目链接:https://www.nowcoder.com/acm/contest/203/I?tdsourcetag=s_pcqq_aiomsg
来源:牛客网
思路:我们用用fa[i]表示距离i最近的大都市,dis[i]表示i距离该大都市的距离。我们先把所有大都市加入初始点,然后跑Dijkstra,如果某一点到另一个大都市距离更近,那么更新dis和fa。如果取边时,边的两边分别属于不同的两个大都市,说明两个大都市连通了,那么更新答案。
代码:
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
const int maxn = + ;
const int seed = ;
const ll MOD = 1e9 + ;
const ll INF = 1e17;
using namespace std;
struct Edge{
int to, next;
ll w;
}edge[maxn << ];
struct qnode{
int u;
ll c;
qnode(int _u = , ll _c = ):u(_u), c(_c){}
bool operator < (const qnode &r) const{
return r.c < c;
}
};
int n, m, p, tot, head[maxn], big[maxn], fa[maxn], id[maxn];
ll dis[maxn], ans[maxn];
void addEdge(int u, int v, ll w){
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
void Dijkstra(){
memset(fa, -, sizeof(fa));
for(int i = ; i <= n; i++) dis[i] = INF;
for(int i = ; i < p; i++) ans[i] = INF;
priority_queue<qnode> que;
while(!que.empty()) que.pop();
for(int i = ; i < p; i++){
dis[big[i]] = ;
fa[big[i]] = big[i];
que.push(qnode(big[i], ));
}
qnode temp;
while(!que.empty()){
temp = que.top();
que.pop();
int u = temp.u;
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to;
ll w = edge[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
fa[v] = fa[u];
que.push(qnode(v, dis[v]));
}
else if(fa[u] != fa[v] && fa[v] != -){
ans[id[fa[u]]] = min(ans[id[fa[u]]], dis[u] + dis[v] + w);
ans[id[fa[v]]] = min(ans[id[fa[v]]], dis[u] + dis[v] + w);
}
}
}
}
int main(){
int u, v;
ll w;
scanf("%d%d%d", &n, &m, &p);
memset(head, -, sizeof(head));
tot = ;
for(int i = ; i < p; i++){
scanf("%d", &u);
big[i] = u;
id[u] = i;
}
for(int i = ; i < m; i++){
scanf("%d%d%lld", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
Dijkstra();
for(int i = ; i < p; i++){
if(i != ) printf(" ");
printf("%lld", ans[i]);
}
printf("\n");
return ;
}