pku1511 Invitation Cards

http://poj.org/problem?id=1511
图论，最短路，SPFA
求所有点到1
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #define N 1000100
 5 
 6 using namespace std;
 7 
 8 int n, m, src;
 9 int x[N], y[N], len[N];
10 int dist[N];
11 bool inQue[N];
12 queue<int> que;
13 const int inf = 1<<30;
14 vector<pair<int, int> > g[N];
15 
16 void spfa()
17 {
18     int i;
19     for(i=0; i<N; i++)
20     {
21         inQue[i] = false;
22         dist[i] = inf;
23     }
24     dist[src] = 0;
25     while(!que.empty())
26     {
27         que.pop();
28     }
29     que.push(src);
30     inQue[src] = true;
31     while(!que.empty())
32     {
33         int u = que.front();
34         que.pop();
35         for(i=0; i<g[u].size(); i++)
36         {
37             if(dist[u] + g[u][i].second < dist[g[u][i].first])
38             {
39                 dist[g[u][i].first] = dist[u] + g[u][i].second;
40                 if(!inQue[g[u][i].first])
41                 {
42                     inQue[g[u][i].first] = true;
43                     que.push(g[u][i].first);
44                 }
45             }
46         }
47         inQue[u] = false;
48     }
49 }
50 
51 
52 int main()
53 {
54     int t, i, j;
55     long long result;
56     scanf("%d", &t);
57     while(t-- && scanf("%d%d", &n, &m))
58     {
59         for(i=1; i<=n; i++)
60         {
61             g[i].clear();
62         }
63         for(i=1; i<=m; i++)
64         {
65             scanf("%d%d%d", x+i, y+i, len+i);
66         }
67         for(i=1; i<=m; i++)
68         {
69             g[x[i]].push_back(make_pair(y[i], len[i]));
70         }
71         result = 0;
72         src = 1;
73         spfa();
74         for(i=2; i<=n; i++)
75         {
76             result += dist[i];
77         }
78         for(i=1; i<=n; i++)
79         {
80             g[i].clear();
81         }
82         for(i=1; i<=m; i++)
83         {
84             g[y[i]].push_back(make_pair(x[i], len[i]));
85         }
86         src = 1;
87         spfa();
88         for(i=2; i<=n; i++)
89         {
90             result += dist[i];
91         }
92         printf("%lld\n", result);
93     }
94     return 0;
95 }