poj3268Silver Cow Party

从终点进行两遍dijkstra，两遍之间要把矩阵转置一下。

最后遍历各点更新最大值。

dijkstra：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int maxn=1010;
 8 const int inf=9999999;
 9 int n,m,xx;
10 int u,v,w;
11 int pic[maxn][maxn];
12 int vis[maxn];
13 int d1[maxn],d2[maxn];
14 void dijkstra(int *d)
15 {
16      memset(vis,0,sizeof(vis));
17     for(int i=1;i<=n;i++)
18         d[i]=(i==xx?0:inf);
19         for(int i=0;i<n;i++)
20         {
21             int m=inf,x;
22             for(int y=1;y<=n;y++)
23                 if(!vis[y]&&d[y]<m) m=d[x=y];
24             vis[x]=1;
25             for(int y=1;y<=n;y++)
26             {
27                 if(!vis[y]&&d[y]>d[x]+pic[x][y]) {
28                     d[y]=d[x]+pic[x][y];
29                 }
30             }
31         }
32 }
33 void trans()   //矩阵转置
34 {
35     for(int i=1;i<=n;i++)
36         for(int j=1;j<=i;j++)
37         swap(pic[i][j],pic[j][i]);
38 }
39 int main()
40 {
41     while(scanf("%d%d%d",&n,&m,&xx)!=EOF)
42     {
43         for(int i=1;i<=n;i++)
44             for(int j=1;j<=n;j++)
45                 pic[i][j]=inf;
46         for(int i=0;i<m;i++)
47         {
48             scanf("%d%d%d",&u,&v,&w);
49             pic[u][v]=w;
50         }
51         dijkstra(d1);
52         trans();
53         dijkstra(d2);
54        int  ans=-1;
55         for(int i=1;i<=n;i++)
56         {
57             if(d1[i]!=inf&&d2[i]!=inf) ans=max(ans,d1[i]+d2[i]);
58         }
59         printf("%d
",ans);
60     }
61 }

spfa：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int maxn=1010;
 8 const int inf=0x3f3f3f3f;
 9 int n,m,xx;
10 int u,v,w;
11 int pic[maxn][maxn];
12 int inq[maxn];
13 int que[maxn<<1];
14 int d1[maxn],d2[maxn];
15 
16 
17 void trans()
18 {
19     for(int i=1;i<=n;i++)
20         for(int j=1;j<=i;j++)
21         swap(pic[i][j],pic[j][i]);
22 }
23 
24 void spfa(int *d)
25 {
26    for(int i=1;i<=n;i++)
27        d[i]=inf;
28 
29     memset(inq,0,sizeof(inq));
30     d[xx]=0;
31     int tail=-1;
32     que[++tail]=xx;
33     inq[xx]=1;
34     while(tail!=-1)
35     {
36         int cur=que[tail];
37         tail--;
38         inq[cur]=0;
39         for(int i=1;i<=n;i++)
40             if(d[i]>d[cur]+pic[cur][i])
41         {
42             d[i]=d[cur]+pic[cur][i];
43             if(inq[i]==0) 
44             {
45                 que[++tail]=i;
46                 inq[i]=1;
47             }
48         }
49     }
50 }
51 
52 
53 int main()
54 {
55     while(scanf("%d%d%d",&n,&m,&xx)!=EOF)
56     {
57         for(int i=1;i<=n;i++)
58             for(int j=1;j<=n;j++)
59                 pic[i][j]=inf;
60         for(int i=0;i<m;i++)
61         {
62             scanf("%d%d%d",&u,&v,&w);
63             pic[u][v]=w;
64         }
65         spfa(d1);
66         trans();
67         spfa(d2);
68        int  ans=-1;
69         for(int i=1;i<=n;i++)
70         {
71             if(d1[i]!=inf&&d2[i]!=inf) ans=max(ans,d1[i]+d2[i]);
72         }
73         printf("%d
",ans);
74     }
75 }