poj 1511(spfa)

---恢复内容开始---

一个spfa类的模板水题。

题意：就是求从1到n个点的来回的所有距离和。

对spfa类的题还是不太熟练，感觉还是做少了，多水水这种题。

思路：也就是双向的spfa就行了。这里就是注意答案要用long long 类型来存就可以。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #define maxn 1000010
 5 #define inf 0x3f
 6 
 7 using namespace std;
 8 
 9 int m,n,pos,a[ maxn ],b[ maxn ],c[ maxn ],head[ maxn ];
10 
11 long long ans , dist[ maxn ];
12 
13 bool vis[ maxn ];
14 
15 struct note {
16     int v,w,next;
17 }edge[maxn];
18 
19 void init()
20 {
21     pos = 1;
22     memset( dist , inf , sizeof( dist ) );
23     memset( head , -1 , sizeof( head ) );
24     memset( vis , false ,sizeof( vis ) );
25 }
26 
27 void add(int x,int v,int w)    //这是用数组来构建的一个邻接表。不懂可以在纸上模拟一次就行。
28 {
29     edge[ pos ].v = v;
30     edge[ pos ].w = w;
31     edge[ pos ].next = head[ x ];
32     head[ x ] = pos++;
33 }
34 
35 void spfa()     //标准的spfa模板。如果可能有负权回路的话，那就加个num数组来判断。
36 {
37     queue<int >s;
38     s.push(1);
39     vis[ 1 ] = true;
40     dist[ 1 ] = 0;
41     while(!s.empty())
42     {
43         int tmp = s.front();
44         s.pop();
45         vis [ tmp ] = false;
46         for( int i = head[ tmp ] ; i != -1 ; i = edge[ i ].next )
47         {
48             if( dist[ edge[ i ].v ] > dist[ tmp ] + edge[ i ].w)
49             {
50                 dist[ edge[ i ].v ] = dist[ tmp ] + edge[ i ].w;
51                 if( !vis[ edge[ i ].v ] )
52                 {
53                     s.push( edge[ i ].v );
54                     vis[ edge[ i ].v ] =true;
55                 }
56 
57             }
58 
59         }
60     }
61     for( int i = 1 ; i <= m ; i++ )
62         ans += dist[ i ];
63 }
64 
65 int main()
66 {
67   //  freopen("in.txt","r",stdin);
68     int t;
69     scanf("%d",&t);
70     while(t--)
71     {
72         ans = 0;
73         scanf("%d%d",&m,&n);
74         init();              //两次spfa，正向和反向。
75         for( int i = 1 ; i <= n ; i++ )
76         {
77             scanf("%d%d%d",&a[ i ],&b[ i ],&c[ i ]);
78             add( a[ i ] , b[ i ] , c[ i ] );
79         }
80         spfa();
81         init();
82         for( int i = 1 ; i <= n ; i++ )
83             add( b[ i ] , a[ i ] , c[ i ] );
84         spfa();
85         printf("%lld
",ans);
86     }
87     return 0;
88 }