[floyd][usaco.09.DEC.][jzyzoj1218][过路费]——floyd新姿势get

　　这道题并没有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 }

AC代码

[floyd][usaco.09.DEC.][jzyzoj1218][过路费]——floyd新姿势get

相关推荐