首页 > 其他 > 详细

Newcoder Metropolis(多源最短路 + Dijkstra堆优化)题解

时间:2018-10-19 00:42:21      阅读:133      评论:0      收藏:0      [点我收藏+]

题目链接: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 = 200000 + 10;
const int seed = 131;
const ll MOD = 1e9 + 7;
const ll INF = 1e17;
using namespace std;
struct Edge{
    int to, next;
    ll w;
}edge[maxn << 1];
struct qnode{
    int u;
    ll c;
    qnode(int _u = 0, ll _c = 0):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, -1, sizeof(fa));
    for(int i = 0; i <= n; i++) dis[i] = INF;
    for(int i = 0; i < p; i++) ans[i] = INF;
    priority_queue<qnode> que;
    while(!que.empty()) que.pop();
    for(int i = 0; i < p; i++){
        dis[big[i]] = 0;
        fa[big[i]] = big[i];
        que.push(qnode(big[i], 0));
    }
    qnode temp;
    while(!que.empty()){
        temp = que.top();
        que.pop();
        int u = temp.u;
        for(int i = head[u]; i != -1; 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] != -1){
                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, -1, sizeof(head));
    tot = 0;
    for(int i = 0; i < p; i++){
        scanf("%d", &u);
        big[i] = u;
        id[u] = i;
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d%lld", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    Dijkstra();
    for(int i = 0; i < p; i++){
        if(i != 0) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");
    return 0;
}

 

Newcoder Metropolis(多源最短路 + Dijkstra堆优化)题解

原文:https://www.cnblogs.com/KirinSB/p/9813958.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!