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

 

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

 

#include
      
       #include
       
        using namespace std;using namespace __gnu_pbds;const int maxn = 1e6 + 10;const int INF  = 0x3f3f3f3f;typedef pair
        
          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
         
          
           ,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\n", ans);    }    return 0;}