过路费

admin管理员组

文章数量:1794759

过路费

　　问题描述：

　　有一天你来到了一个奇怪的国家，它有 N 个城市，城市之间有若干条双向道路连接，每条道路都有一定的费用，经过城市也要一定的费用。从一个城市到达另一个城市的总花费为路径上费用最大的城市费用（包括起点和终点）加上路径上所有的道路的费用。给出 Q 次询问，分别回答每次询问中两城市间的最少花费。保证城市之间可以互达。

　　这道题主要是需要了解Floyd的更新方法。

　　对于Floyd，由于我们第一层循环枚举中转点k，对于 i ，j 的更新，我们会看 i ---> k ，k ---> j，换句话说，我们在考虑 i 到 j 的路径的时候，只会经过｛1，2，3，...，k｝U｛i，j｝中的点。

　　所以先把点权从小到大排序，那么此时路径上最大的点权就是 i ，j ， k 中的一个了。

　　这样的话，我们就可以直接得到现在路径中点权的最大值，剩下的就是 floyd 了。

　　代码（BZOJ删了这道题，写完没处交，反正很短，直接复制）：

#include<stdio.h>
#include<algorithm>
#define MAXN 305
using namespace std;int N,M,Q,Map[MAXN][MAXN],Ans[MAXN][MAXN],Hash[MAXN];struct node
{int c,id;
} V[MAXN];
bool operator<(node x,node y)
{return x.c<y.c;
}int main()
{int i,j,k,x,y,z;scanf("%d%d",&N,&M);for(i=1; i<=N; i++)scanf("%d",&V[i].c),V[i].id=i;sort(V+1,V+N+1);for(i=1; i<=N; i++)Hash[V[i].id]=i;for(i=1; i<=N; i++)for(j=1; j<=N; j++)Map[i][j]=Ans[i][j]=1e9;for(i=1; i<=N; i++)Map[i][i]=0;for(i=1; i<=M; i++){scanf("%d%d%d",&x,&y,&z);x=Hash[x];y=Hash[y];Map[x][y]=min(Map[x][y],z);Map[y][x]=Map[x][y];}for(k=1; k<=N; k++)for(i=1; i<=N; i++)for(j=1; j<=N; j++){Map[i][j]=min(Map[i][k]+Map[k][j],Map[i][j]);Ans[i][j]=min(Ans[i][j],Map[i][j]+max(V[i].c,max(V[j].c,V[k].c)));}scanf("%d",&Q);for(i=1; i<=Q; i++){scanf("%d%d",&x,&y);x=Hash[x];y=Hash[y];printf("%d\n",Ans[x][y]);}return 0;
}

{1,2,3,…,k}⋃{i，j} {1,2,3,…,k}⋃{i，j}

中的点！

转载于:.html

本文标签： 过路费