POJ-1511 Invitation Cards---Dijkstra+队列优化+前向星正向反向存图

题目链接：

题目大意：

给定节点数n,和边数m,边是单向边.

问从1节点出发到2,3,...n 这些节点路程和从从这些节点回来到节点1的路程和最小值。

n，m不超过1e6

思路：

和POJ-3268是一样的，大概思路都是正向从源点求最短路，然后把图反向，再从源点求最短路，但是这道题是它的进阶版本，由于点数过多，不可以用邻接矩阵存图，这里用前向星存图，同时存下两张图，一张正向，一张反向。Dijkstra算法用队列优化，注意用long long存答案和dist最短路距离。其他的就是模板题了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #include<sstream>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6 + ;

 const int INF = 1e9 + ;

 int T, n, m, cases;

 struct edge

 {

     int next, u, v, w;

 };

 edge a[][maxn];//a[0][]存正边 a[1][]存反边

 ll d[maxn];

 int head[][maxn];

 bool v[maxn];

 void init()

 {

     memset(head, -, sizeof(head));

 }

 struct HeapNode

 {

     int d, u;//d是距离，u是顶点

     HeapNode(){}

     HeapNode(int d, int u):d(d), u(u){}

     bool operator <(const HeapNode & a)const

     {

         return d > a.d;

     }

 };

 void dijkstra(int cnt)

 {

     priority_queue<HeapNode>q;

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

     d[] = ;

     memset(v, , sizeof(v));

     q.push(HeapNode(, ));

     while(!q.empty())

     {

         HeapNode now = q.top();

         q.pop();

         int u = now.u;

         if(v[u])continue;

         v[u] = ;//标记

         for(int i = head[cnt][u]; ~i; i = a[cnt][i].next)

         {

             edge& e = a[cnt][i];

             int v = e.v, w = e.w;

             if(d[v] > d[u] + w)

             {

                 d[v] = d[u] + w;

                 q.push(HeapNode(d[v], v));

             }

         }

     }

 }

 int main()

 {

     scanf("%d", &T);

     while(T--)

     {

         init();

         scanf("%d%d", &n, &m);

         int u, v, w;

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

         {

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

             //正向存边

             a[][i].u = u;

             a[][i].v = v;

             a[][i].w = w;

             a[][i].next = head[][u];

             head[][u] = i;

             //反向存边

             a[][i].u = v;

             a[][i].v = u;

             a[][i].w = w;

             a[][i].next = head[][v];

             head[][v] = i;

         }

         ll ans = ;

         dijkstra();

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

         dijkstra();

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

         cout<<ans<<endl;

     }

     return ;

 }