求3个点之间联通的最短线路长度。注意支撑点不一定在这3个点中。因此需要分别求3次到这3个点(x,y,z)的单源最短路径，然后遍历每个节点j（支撑点）,求dis(x,j)+dis(y,j)+dis(z,j)的最小值。
这题最多求 3*50(查询次数)次单源最短路，小于500，所以用Floyd求所有的单源最短路容易超时。
此处点数较少可以用Dijkstra，如果点数较大无法使用邻接矩阵时，可以采用另一种方法更为快速,spfa（复杂度为K*E,可以证明K在2左右）但是时间效率不及Dijkstra稳定，实际应用中很多用Dijkstra，它利用了松弛原理（三角型2边之和大于第3边），只要在松弛时维护一个队列，并且用标记访问数组防止元素重复入队即可。spfa是bellman-ford的队列优化，每次不用枚举所有的点，而是使用队列来更新点。用spfa的前提是边权为正。spfa判断负权边的方法是：如果有一个点超过|V|次入队列。可以用path[u] = v来存储松弛时通过v更新u,u之前的点是v,如果打印路径，可以用递归的方法克服逆序问题。spfa的改进方法为LLL,SLF。
spfa参考：
解题报告在浙大某大牛那
http://watashi.ws/blog/1492/zojmonthly1009/
1
#include<stdio.h>
2#include<vector>
3#include<queue>
4using namespace std;
5#define MAXN 10002
6#define MAXM 502
7//#define clr(a) memset(a,0,sizeof(a))
8#define INF 999999
9struct node
10
{
11
node (int v0, int dis0):v(v0),dis(dis0){}
12
int v;
13 int dis;
14
};
15vector<node> map[MAXM];
16bool visit[MAXM];
17int m;
18void spfa(int x,int dis[])
19{
20 int i;
21 //clr(visit);
22 visit[x] = true;
23 for(i = 1; i <= m; i++)
24 {
25 dis[i] = INF;
26 visit[i] = false;
27
}
28 dis[x] = 0;
29 queue<int> q;
30 q.push(x);
31 while(!q.empty())
32 {
33 int u = q.front();
34 q.pop();
35 visit[u] = false;
36 for(i = 0; i < map[u].size(); i++)
37 {
38 node p = map[u][i];
39 if(dis[p.v] > (dis[u] + p.dis))
40 {
41 dis[p.v] = dis[u] + p.dis;
42 if(!visit[p.v])
43 {
44 visit[p.v] = true;
45 q.push(p.v);
46 }
47 }
48 }
49 }
50}
51int main()
52{
53 int n,L,q,x,y,z,a,b,len,count=1,i,j,min;
54 int t[MAXN],dis1[MAXM],dis2[MAXM],dis3[MAXM];
55 while(scanf("%d %d %d",&n,&m,&L)!=EOF)
56 {
57 printf("Case #%d\n",count++);
58 for(i = 0; i < n; i++)
59 {
60 scanf("%d",&t[i]);
61 }
62 for(i = 1; i <= m; i++ )
63 map[i].clear();
64 for(i = 0; i < L; i++)
65 {
66 scanf("%d %d %d",&a,&b,&len);
67 map[a].push_back(node(b,len));
68 map[b].push_back(node(a,len));
69 }
70 scanf("%d",&q);
71 for(i = 1; i <= q; i++)
72 {
73 scanf("%d %d %d",&x,&y,&z);
74 spfa(t[x-1],dis1);
75 spfa(t[y-1],dis2);
76 spfa(t[z-1],dis3);
77 min = INF;
78 for(j = 1; j <= m; j++)
79 {
80 if(min > (dis1[j] + dis2[j] + dis3[j]))
81 min = (dis1[j] + dis2[j] + dis3[j]);
82 }
83 if(min != INF)
84 printf("Line %d: The minimum cost for this line is %d.\n",i,min);
85 else
86 printf("Line %d: Impossible to connect!\n",i);
87 }
88 }
89
90}