P2966 P2966 [USACO09DEC]Cow Toll Paths G

P2966 [USACO09DEC]Cow Toll Paths G

题目本体

观察题目：

很容易想到多元最短路：

(floyd)

注意先给点权排序，这样后面只需要考虑边权了。

这点的思路上和导弹拦截十分相似。

用一个基础(dp)进行比较得出答案。

最后输出。

(AC)代码

#include<bits/stdc++.h>
using namespace std;

int n,m,q;
int ans[1005][1005],diss[1005][1005];

const int inf = 0x3f3f3f3f;

struct node{
	int val,dis;
}c[1005];

bool cmp (node x, node y){
	return x.val < y.val;
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&c[i].val);
		c[i].dis = i;
	}
	sort(c+1,c+n+1,cmp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) diss[i][j]=0;
			else diss[i][j]=inf;
		}
	}
	memset(ans,0x3f,sizeof(ans));
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		diss[u][v]=min(diss[u][v],w);
		diss[v][u]=min(diss[v][u],w);
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				diss[c[i].dis][c[j].dis]=min(diss[c[i].dis][c[j].dis],diss[c[i].dis][c[k].dis]+diss[c[k].dis][c[j].dis]);
				ans[c[i].dis][c[j].dis]=min(ans[c[i].dis][c[j].dis],diss[c[i].dis][c[j].dis]+max(c[i].val,max(c[j].val,c[k].val)));
			}
		}
	}
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d
",ans[a][b]);
	}
	return 0;
}