POJ 1511 Invitation Cards ( 双向单源最短路 || 最小来回花费 )

题意 : 给出 P 个顶点以及 Q 条有向边，求第一个点到其他各点距离之和+其他各点到第一个点的距离之和的最小值

分析 : 不难看出 min( 第一个点到其他各点距离之和+其他各点到第一个点的距离之和 ) = min( 第一个点到其他各点距离之和) + min( 其他各点到第一个点的距离之和 )，前者较为简单，建好图后直接跑一遍最短路即得，关键在于后者怎么方便的求出来。这里利用到了一个逆向思维，如果将所有的有向边反过来，那么就能求出其他点到源点的最短路了，那么只要存储两种边，一个正向边（即题目所给）然后存一组反向边，两种建出来的图各自去跑一遍最短路最后相加即为结果

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
const int maxn = 1e6 + 10;
const int INF  = 0x3f3f3f3f;
typedef pair<int, int> pii;
struct EDGE{ int v, nxt, w; };
EDGE Edge[2][maxn];
int cnt, N, M, Head[2][maxn];

inline void init()
{
    for(int i=0; i<=N; i++)
        Head[0][i] = Head[1][i] = -1;
    cnt = 0;
}

inline void AddEdge(int from, int to, int weight, int flag)
{
    Edge[flag][cnt].v = to;
    Edge[flag][cnt].nxt = Head[flag][from];
    Edge[flag][cnt].w = weight;
    Head[flag][from] = cnt++;
}

int Dis[maxn];

int Dijkstra(int flag)
{
    for(int i=1; i<=N; i++)
        Dis[i] = INF;
    Dis[1] = 0;
    __gnu_pbds::priority_queue<pii,greater<pii>,pairing_heap_tag > Heap;
    Heap.push(make_pair(0, 1));
    pii Top;
    while(!Heap.empty()){
        Top = Heap.top(); Heap.pop();
        if(Dis[Top.second] != Top.first) continue;
        for(int i=Head[flag][Top.second]; i!=-1; i=Edge[flag][i].nxt){
            int Eiv = Edge[flag][i].v;
            if(Dis[Eiv] > Dis[Top.second] + Edge[flag][i].w){
                Dis[Eiv] = Dis[Top.second] + Edge[flag][i].w;
                Heap.push(make_pair(Dis[Eiv], Eiv));
            }
        }
    }
    int ret = 0;
    for(int i=2; i<=N; i++)
        ret += Dis[i];
    return ret;
}

int main(void)
{
    int nCase;
    scanf("%d", &nCase);
    while(nCase--){
        scanf("%d %d", &N, &M);
        init();
        int from, to, weight;
        while(M--){
            scanf("%d %d %d", &from, &to, &weight);
            AddEdge(from, to, weight, 0);
            AddEdge(to, from, weight, 1);
        }
        int ans = 0;
        ans += Dijkstra(0);
        ans += Dijkstra(1);
        printf("%d
", ans);
    }
    return 0;
}