【最短路】道路重建 @upcexam5797

时间限制: 1 Sec 内存限制: 128 MB 题目描述
小L的家乡最近遭遇了一场洪水，城市变得面目全非，道路也都被冲毁了。生活还要继续，于是市政府决定重建城市中的道路。
在洪水到来前，城市中共有n个区域和m条连接这些区域的双向道路，道路连通了所有的区域，为了方便人们的出行，只能重建这些原有的道路，
不能建新的道路。编号为s的区域是市政广场，市政府希望重建的道路能够使得所有区域到市政广场的最短路与受灾前保持不变，同时为了节约救灾
经费，还要使得修建的所有道路的长度和尽可能小。小L为了拯救心爱的家乡，决定站出来，成为优秀的青年理论计算机科
学家，于是马上投入到了对这个问题的研究中。你能帮帮小L吗？

输入
第一行两个整数n和m，表示区域与道路的个数。
接下来m行，每行三个正整数u，v和w，描述一条连接u和v、长为w的道路。最后一行，一个正整数s，表示市政广场的编号。

输出
输出一个整数，表示最小长度和。样例输入 5 7 1 2 1 2 3 4 2 4 2 4 3 2 5 2 2 4 5 1 5 1 1
2 样例输出 6 提示最优方案是重建1-2,1-5,2-4,4-3的道路，此时所有区域到达区域2的最短路分别是1, 0, 4, 2,
2，道路长度和是1 + 1 + 2 + 2 = 6。对于20%的数据，n ≤ 10, m ≤ 20；对于另外30%的数据，边权不超过2；
对于100%的数据，1 ≤ n ≤ 105, n − 1 ≤ m ≤ 2 ∗ 105, 1 ≤ w ≤ 109。

来源 2018山东冬令营

先跑一遍Dijkstra，求出原点到每个点的最短路径长度d[i]，
再一模一样跑一遍Dijkstra,只不过在每次更新操作时，维护每个点的最小入度值。
具体就是如果dd[u]（当前求得的原点到u的最短路长度）+e(u,v).w == d[v]（第一次求得的最短路），
就维护d2[v] = min(d2[v],e(u,v).w);

#define FILE() freopen("../../in.txt","r",stdin)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//const int MOD = 1e9+7;

const int maxn = 100005,maxm = 200005;

const ll INF = 1e16+5;

int n,m,head[maxn],cnt;

ll d[maxn],dd[maxn],d2[maxn];

struct edge {

    int v,nex;

    ll w;

} ed[maxm*2];

struct node1{

    int num,len;

};

struct node2{

    int num,len;

};

bool operator < (node1 a,node1 b){

    return d[a.num]>d[b.num];

}

bool operator < (node2 a,node2 b){

    return dd[a.num]>dd[b.num];

}

priority_queue <node1> q;

priority_queue <node2> qq;

void addedge(int _u,int _v,ll _w) {

    cnt++;

    ed[cnt].v = _v;

    ed[cnt].w = _w;

    ed[cnt].nex = head[_u];

    head[_u] = cnt;

}

void dij1(int start) {

    for(int i=1;i<=n;i++)d[i] = INF;

    d[start] = 0;

    while(!q.empty())q.pop();

    q.push((node1){start,0});

    while(!q.empty()) {

        int cur = q.top().num,len = q.top().len;

        q.pop();

        if(d[cur]<len)continue;

        for(int i=head[cur]; i; i=ed[i].nex) {

            int v=ed[i].v;

            if(d[v]>d[cur]+ed[i].w){

                d[v] = d[cur]+ed[i].w;

                q.push((node1){v,d[v]});

            }

        }

    }

}

void dij2(int start){

    for(int i=1;i<=n;i++)dd[i] = d2[i] = INF;

    dd[start] = d2[start] = 0;

    while(!qq.empty())qq.pop();

    qq.push((node2){start,0});

    while(!qq.empty()) {

        int cur = qq.top().num,len = qq.top().len;

        qq.pop();

        if(dd[cur]<len)continue;

        for(int i = head[cur];i;i=ed[i].nex){

            int v=ed[i].v;

            if(dd[v]>dd[cur]+ed[i].w){

                dd[v] = dd[cur]+ed[i].w;

                qq.push((node2){v,dd[v]});

            }

            if(d[v]==dd[cur]+ed[i].w){

                d2[v] = min(d2[v],ed[i].w);

            }

        }

    }

}

int main() {

//    FILE();

//    freopen("../../out.txt","w",stdout);

    cin>>n>>m;

    for(int i=0; i<m; i++) {

        int u,v;

        ll w;

        scanf("%d%d%lld",&u,&v,&w);

        addedge(u,v,w);

        addedge(v,u,w);

    }

    int s;

    cin>>s;

    dij1(s);

    dij2(s);

    ll sum = 0;

    for(int i=1;i<=n;i++)sum+=d2[i];

    cout<<sum<<endl;

    return 0;

}

巴特西

【最短路】道路重建 @upcexam5797

最新文章

热门文章