COJ1024(Mining)

题目大意：给定一个无向图，指定2个起点s1和s2和一个终点t，2个人分别从s1和s2出发，目的地是t，求两人的最短路径的最大公共长度（在保证两人均走最短路的前提下使两人一起走的路径最长）。

分析：只要两人会合后，就一定会一起走完剩下的全程。所以大体思路是枚举可能的会合点，在判断某个点是否是可能的会合点时，判断这个点是否都是两个人的最短路径上的点即可。求最短路时用到dijkstra。

View Code

 1 #include <stdio.h>
 2 #include <memory.h>
 3 #define N 1000
 4 #define INF 0x7fffff
 5 #define MIN(a,b)  ((a)<(b)?(a):(b))
 6 int g[N][N],dist1[N],dist2[N],dist3[N],n,m;
 7 char vis[N];
 8 void dijkstra(int u,int dist[])
 9 {
10   int v,i,k,min;
11   memset(vis,0,sizeof(vis));
12   for(i=0;i<n;i++)  dist[i]=(i==u?0:INF);
13   for(i=0;i<n;i++)
14   {
15     min=INF;
16     for(v=0;v<n;v++)  if(!vis[v]&&dist[v]<=min) min=dist[k=v];
17     vis[k]=1;
18     for(v=0;v<n;v++)  dist[v]=MIN(dist[v],dist[k]+g[k][v]);
19   }
20 }
21 int main()
22 {
23   int i,j,t,u1,u2,u3,u,v,d,ans;
24   scanf("%d",&t);
25   while(t--)
26   {
27     scanf("%d%d%d%d%d",&n,&u1,&u2,&u3,&m);
28     u1--,u2--,u3--;
29     for(i=0;i<n;i++)
30     {
31       for(j=i+1;j<n;j++)  g[i][j]=g[j][i]=INF;
32     }
33     for(i=0;i<m;i++)
34     {
35       scanf("%d%d%d",&u,&v,&d),u--,v--;
36       g[u][v]=g[v][u]=d;
37     }
38     dijkstra(u1,dist1);
39     dijkstra(u2,dist2);
40     dijkstra(u3,dist3);
41     ans=0;
42     j=u1;
43     for(i=0;i<n;i++)
44     {
45       if(dist1[i]>=ans&&dist1[u2]==dist1[i]+dist2[i]&&dist1[u3]==dist1[i]+dist3[i]) ans=dist1[j=i];
46     }
47     printf("%d %d %d\n",ans,dist2[j],dist3[j]);
48   }
49   return 0;
50 }