看不到的请用firefox浏览器。
【题目大意】给出一个无向图，点有点权，边有边权。然后有Q个询问(X,Y)，表示求一条从X到Y的路径，其总代价为路上边权只和加上路径上点权最大的一个点的点权。询问就使这个总代价最少是多少？
【算法分析】
翻开《算法艺术与信息学竞赛》第308页就有这个题目。
我们假定了K为点权最大的点，那么显然，对于询问(X,Y)：W=D[X,K]+D[K,Y]+COST[K]。
其中D[X,K]和D[K,Y]表示删除权值比K大的点以后的最短路。
由于是无向图，再转变一下。
W=D[K,X]+D[K,Y]+COST[K]。
到了这一步。。。大家都知道怎么打表了吧。。。
我们就先预处理出D[i,j]表示从第i个出发，且所有点权>COST[i]的点都已删掉以后，到达j的最短路。
这可以用SPFA实现，复杂度O(NM)
然后打表，复杂度O(N^3)
【其他】我居然WA了4次，因为同一个问题：我把Case #xxx看成是题目给的方便你看的。。。没有输出。。。我那叫一个纠结吖~拿块豆腐撞死自己算了
【code】
#include
#define E 1000000
#define N 1000
using namespace std;
struct gtp{int x,y,w,next;}g[E];
int n,m,q,e,ls[N],ans[N][N],Vp[N],dist[N][N];
int d[N],list[N],v[N];
void add(int x,int y,int w){
e++;
g[e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}
void init(){
memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++) scanf("%d",&Vp[i]);
e=0;
for (int i=1;i<=m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
}
void spfa(int st){
int head=0,tail=1; list[1]=st;
memset(v,0,sizeof(v));
for (int i=1;i<=n;i++) d[i]=INF;
d[st]=0; v[st]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t!=0;t=g[t].next)
if (Vp[g[t].y]<=Vp[st] && d[g[t].x]+g[t].w
if (v[g[t].y]==0){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
}
void work(){
for (int i=1;i<=n;i++){
spfa(i);
for (int j=1;j<=n;j++) dist[i][j]=d[j];
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
ans[i][j]=INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++){
int tmp;
if (dist[k][i]==INF || dist[k][j]==INF) tmp=INF;
else tmp=dist[k][i]+dist[k][j]+Vp[k];
ans[i][j]=min(ans[i][j],tmp);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (ans[i][j]==INF) ans[i][j]=-1;
}
void print(){
for (int i=1;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%dn",ans[x][y]);
}
}
int main(){
int test=0;
for (;;){
scanf("%d%d%d",&n,&m,&q);
if (n+m+q==0) break;
test++;
if (test>1) printf("n");
init();
work();
printf("Case #%dn",test);
print();
}
return 0;
}