一遍SPFA求去的最短路徑，把圖的邊逆向，再一遍SPFA，求出回來的最短路徑...
SPFA其實是Bellman-Ford使用隊列的優化
1
#include<iostream>
2#include<queue>
3using namespace std;
4#define INF 2147483647 //2,147,483,647
5#define MAXP 1000000 //1,000,000
6#define MAXSUM 1000000000 //1,000,000,000
7
8struct Edge
9
{
10
//int src;
11 int vertex;
12 int weight;
13 Edge *next;
14
};
15
16Edge edge[MAXP*2+1];
17Edge *go[MAXP+1];
18Edge *back[MAXP+1];
19int dis[MAXP+1];
20bool flag[MAXP+1]; //false denote that the vertex is not in the queue
21
22void creatlist(int vn,int en)
23{
24 int s,d,w,i,j;
25 for(i=1;i<=vn;i++)
26
{
27 go[i]=NULL;
28 back[i]=NULL;
29 flag[i]=false;
30
}
31 for(i=1,j=1;i<=en;i++)
32 {
33 scanf("%d%d%d",&s,&d,&w);
34 edge[j].vertex=d;
35 edge[j].weight=w;
36 edge[j].next=go[s];
37 go[s]=&edge[j++];
38
39 edge[j].vertex=s;
40 edge[j].weight=w;
41 edge[j].next=back[d];
42 back[d]=&edge[j++];
43 }
44}
45
46void spfa(Edge *adjlist[],int vn,int src)
47{
48 int i,u,v,tmp;
49 Edge *p;
50 queue<int> Queue;
51 for(i=1;i<=vn;i++)
52 dis[i]=INF;
53 dis[src]=0;
54 Queue.push(src);
55 while(!Queue.empty())
56 {
57 u=Queue.front();
58 Queue.pop();
59 flag[u]=false;
60 p=adjlist[u];
61 while(p!=NULL)
62 {
63 tmp=dis[u]+p->weight;
64
65 v=p->vertex;
66 if(dis[v] > tmp)
67 {
68 dis[v]=tmp;
69 if(flag[v]==false)
70 {
71 Queue.push(v);
72 flag[v]=true;
73 }
74 }
75 /**//*
76 if(dis[p->vertex] > tmp)
77 {
78 dis[p->vertex]=tmp;
79 if(flag[p->vertex]==false)
80 {
81 Queue.push(p->vertex);
82 flag[p->vertex]=true;
83 }
84 }*/
85 p=p->next;
86 }
87 }
88}
89
90int main()
91{
92 int n,p,q,i;
93 __int64 sum;
94 scanf("%d",&n);
95 while(n--)
96 {
97 scanf("%d%d",&p,&q);
98 creatlist(p,q);
99 sum=0;
100 spfa(go,p,1);
101 for(i=1;i<=p;i++)
102 sum+=dis[i];
103 spfa(back,p,1);
104 for(i=1;i<=p;i++)
105 sum+=dis[i];
106 printf("%I64d\n",sum);
107 }
108 return 0;
109}
posted on 2009-04-27 01:31
wyiu 閱讀(136)
評論(0) 編輯 收藏 引用 所屬分類:
POJ