poj 1511 Invitation Cards (链式前向星存图+spfa)
poj 1511 题目链接 题意：和那道奶牛的舞会类似，要求所有点到点1的距离和加上1点到所有点的距离和。 思路：正反存边建两次图，跑两次spfa. 然而用vector会TLE….所以去学习了新的建图方式。。。也就是链式前向星：链式前向星（边表）学习链接 也叫边表。
是一种几乎没有什么缺点的存图方式。。。？ 比起普通的前向星少了个排序。
哦，还有我发现貌似很多人把这个东西叫邻接表。。但是根据这里：几种建图方式
这个东西还是交边表或者链式前向星比较合适。。。？
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月23日 星期一 20时31分19秒
4File Name :code/poj/1511.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E7+7;
34LL d[N];
35bool inq[N];
36int n,m;
37struct Edge
38{
39 int v,w;
40 int nxt;
41}edge1[N],edge2[N]; //反向存一次
42int head1[N],head2[N];
43int cnt;
44void addedge(Edge *edge,int *head,int u,int v,int w)
45{
46 edge[cnt].v = v;
47 edge[cnt].w = w;
48 edge[cnt].nxt = head[u];
49 head[u] = cnt;
50 cnt++;
51}
52
53LL spfa(Edge *edge,int *head)
54{
55
56 ms(inq,false);
57 for ( int i = 0 ; i <= n ; i++) d[i] = 1E18;
58 queue<int>q;
59 q.push(1);
60 d[1] = 0 ;
61 inq[1] = true;
62
63 while (!q.empty())
64 {
65 int u = q.front();
66 q.pop();
67 inq[u] = false;
68
69 for ( int i = head[u]; i !=-1 ;i=edge[i].nxt)
70 {
71 int v = edge[i].v;
72 int w = edge[i].w;
73
74 if (d[v]>d[u]+w)
75 {
76 d[v] = d[u] + w;
77 if (inq[v]) continue;
78 inq[v] = true;
79 q.push(v);
80 }
81 }
82
83// cout<<"sadsad"<<endl;
84
85 }
86 LL res = 0 ;
87 for ( int i = 2 ; i <= n ; i++) res +=d[i];
88 // cout<<"res:"<<res<<endl;
89 //
90
91 return res;
92}
93int main()
94{
95 #ifndef ONLINE_JUDGE
96 freopen("code/in.txt","r",stdin);
97 #endif
98
99// ios::sync_with_stdio(false);
100 int T;
101 scanf("%d",&T);
102 while (T--)
103 {
104 scanf("%d%d",&n,&m);
105 cnt = 0;
106 ms(head1,-1);
107 ms(head2,-1); //忘记初始化，智力-2
108 for ( int i = 1 ; i <= m ; i++)
109 {
110 int u,v,w;
111 scanf("%d%d%d",&u,&v,&w);
112 addedge(edge1,head1,u,v,w);
113 addedge(edge2,head2,v,u,w);
114
115 }
116 // cout<<"sadasdadsasd"<<endl;
117
118 LL ans = 0 ;
119 ans = spfa(edge1,head1)+spfa(edge2,head2);
120 printf("%lld\n",ans);
121
122 }
123
124 #ifndef ONLINE_JUDGE
125 fclose(stdin);
126 #endif
127 return 0;
128}