USACO DEC09 Cow Toll Paths

这题的难点在于如何处理点的权值对最小费用路径的影响。本人也是在看了题解后才弄明白的。

需要用到两个二维数组:cost,dist
dist[i][j]表示i到j的传统意义上的距离
cost[i][j]表示i到j的费用

那么就有cost[i][j] = dist[i][j] + 路径上点的C最大值。

然而，我们并不能在求出最短路前预先知道路径上那个点的C最大啊。既然这样不行，那么我们就指定一个C最大的点吧。

因此，把所有点按照C从小到大排序。然后，对Floyd进行如下修改：让最外层循环的点k的C保持递增，那么对于内层的i和j，max(C[i],C[j],C[k])就是当前路径上C的最大值了。不断更新dist和cost数组。最后读入请求输出对应cost中的值即可。

这个算法用到了Floyd的一个很有趣性质，本人将在以后的文章中进行更深入的探究。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 260
#define INF 1000000000

long dist[MAXN][MAXN];
long cost[MAXN][MAXN];
long c[MAXN],v[MAXN];
int N,M,K;

void init()
{
   int i,j,a,b;
   long t;
   scanf("%d%d%d",&N,&M,&K);
   for(i = 1;i <= N;i ++)
       for(j = 1;j <= N;j ++)
           dist[i][j] = cost[i][j] = INF;
   for(i = 1;i <= N;i ++)
   {
       scanf("%ld",&c[i]);
       v[i] = i;
   }
   for(i = 1;i <= M;i ++)
   {
       scanf("%d%d%ld",&a,&b,&t);
       if(dist[a][b] > t)
           dist[a][b] = dist[b][a] = t;
   }
   for(i = 1;i <= N;i ++)
       for(j = i + 1;j <= N;j ++)
           if(c[v[i]] > c[v[j]])
           {
               t = v[i];v[i] = v[j];v[j] = t;
           }
}

inline long getmax(long a,long b)
{
   if(a > b)    return a;
   return b;
}

void floyd()
{
   int i,j,t,k;
   for(t = 1;t <= N;t ++)
   {
       k = v[t];
       for(i = 1;i <= N;i ++)
           for(j = 1;j <= N;j ++)
           {
               if(dist[i][j] > dist[i][k] + dist[k][j])
                   dist[i][j] = dist[i][k] + dist[k][j];
               if(cost[i][j] > dist[i][j] + getmax(getmax(c[i],c[j]),c[k]))
                   cost[i][j] = dist[i][j] + getmax(getmax(c[i],c[j]),c[k]);
           }
   }
}

void output()
{
   int i,a,b;
   for(i = 1;i <= K;i ++)
   {
       scanf("%d%d",&a,&b);
       printf("%ld\n",cost[a][b]);
   }
}

int main()
{
   freopen("toll.in","r",stdin);
   freopen("toll.out","w",stdout);
   init();
   floyd();
   output();
   fclose(stdout);
   return 0;
}