这道题并没有1A,因为读入邻接矩阵的时候忘了处理重边。。。下面给出题面：
最初看的时候以为纯粹的floyd是可以用的，然而发现并不可以，因为无法查找遍历的最大点，这时候需要转变思想：当你遍历i,j,k时，如何保证权值最大的点就在这三个点之间？我们是不是能将点重组一遍，让所有点按照权值大小排列呢？
这样思路就有了：
如果k从大到小排列的话，不能保证权值在i,j,k之间，因为更新过路径之后权值最大的点已经包含在路径中了。
如果k从小到大排列的话，每次更新最短路，权值最大的点都会在i,j,k之间。
所以我们可以按照这个思路，记录每个点的下标及权值，然后按照权值从小到大排序，所得到的序列就是k应该查找的顺序。
另外处理边的时候需要将最短路与最短路加上最大点权值分开处理。
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 struct points{ 7 int v,p; 8 }point[260];//v为点的值,p为点的坐标 9 int a[260][260],n,m,k,c[260][260],cow[260]; 10 bool mycmp(points x,points y) 11 {return x.v<y.v;} 12 void init() 13 { 14 scanf("%d%d%d",&n,&m,&k); 15 memset(a,0x3f,sizeof(a)); 16 for (int i=1;i<=n;i++) 17 { 18 scanf("%d",&point[i].v); 19 a[i][i]=0; c[i][i]=point[i].v;//点到自身的距离处理，c为边+最大点权值的值，a为边值 20 cow[i]=point[i].v;//另记录每个点的权值，方便查找 21 point[i].p=i; 22 } 23 int x,y,v; 24 for (int i=1;i<=m;i++) 25 { 26 scanf("%d%d%d",&x,&y,&v); 27 a[x][y]=min(a[x][y],v);//处理重边 28 a[y][x]=a[x][y]; 29 } 30 sort(point+1,point+1+n,mycmp);//将点按照从小到大排序 31 } 32 33 void floyd() 34 { 35 for (int x=1;x<=n;x++) 36 { 37 int k=point[x].p; 38 for (int i=1;i<=n;i++) 39 for (int j=1;j<=n;j++) 40 { 41 a[i][j]=a[j][i]=min(a[i][k]+a[k][j],a[i][j]);//更新最短路 42 c[i][j]=c[j][i]=min(c[i][j],a[i][j]+max(max(cow[i],cow[j]),cow[k]));//将当前求得最小值与最短路加上最大权值进行比较并更新 43 } 44 } 45 } 46 47 int main() 48 { 49 freopen("add.in","r",stdin); 50 freopen("add.out","w",stdout); 51 memset(c,0x3f,sizeof(c)); 52 init(); 53 floyd(); 54 int x,y; 55 for (int i=1;i<=k;i++) 56 { 57 scanf("%d%d",&x,&y); 58 printf("%d ",c[x][y]); 59 } 60 return 0; 61 }
这道题对于floyd的理解具有巨大帮助。