bzoj1774[Usaco2009 Dec]Toll 过路费*

bzoj1774[Usaco2009 Dec]Toll 过路费

题意：

n点m边，从点a到b的费用为边权和加a到b经过点的点权最大值，给出q个询问问从a到b的最小费用。n≤200。

题解：

用先对点权排序，接下来用floyd算每两个点的最短路和最小费用，因为点权已经单调了，所以求路径的点权最大值之间比较两个点和中间枚举的那个点的点权最大值即可。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 300
 7 #define INF 0x3fffffff
 8 using namespace std;
 9 
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14     return f*x;
15 }
16 struct nd{int v,id;}nds[maxn]; bool cmp(nd a,nd b){return a.v<b.v;}
17 int num[maxn],g[maxn][maxn],ans[maxn][maxn],n,m,k;
18 int main(){
19     n=read(); m=read(); k=read(); inc(i,1,n)nds[i].v=read(),nds[i].id=i; sort(nds+1,nds+n+1,cmp);
20     inc(i,1,n)num[nds[i].id]=i; inc(i,1,n)inc(j,i+1,n)g[i][j]=ans[i][j]=g[j][i]=ans[j][i]=INF;
21     inc(i,1,m){int x=read(),y=read(),z=read(); g[num[x]][num[y]]=g[num[y]][num[x]]=min(g[num[x]][num[y]],z);}
22     inc(l,1,n)inc(i,1,n)inc(j,1,n){
23         g[i][j]=min(g[i][j],g[i][l]+g[l][j]);
24         ans[i][j]=min(ans[i][j],g[i][j]+max(nds[l].v,max(nds[i].v,nds[j].v)));
25     }
26     inc(i,1,k){int x=read(),y=read(); printf("%d
",ans[num[x]][num[y]]);} return 0;
27 }

20161014