这题其实一开始看的时候我是不会做的……
考虑Floyd,f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
那么我们考虑k的转移顺序，如果让k的点权严格上升,那么转移时增加的点权必定为v[i],v[j]或者v[k]。
那么直接Floyd就可以了。
以后想问题时一定要弄明白算法的本质，不然就会困难重重……
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,K,v[255],dis[255][255],ans[255][255];
struct Point{
int x,y;
friend bool operator<(Point x,Point y){return x.y<y.y;}
}p[255];
int main(){
freopen("1774.in","r",stdin);
freopen("1774.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
memset(dis,127/3,sizeof(dis));
memset(ans,127/3,sizeof(ans));
for(int i=1;i<=n;i++){
scanf("%d",&p[i].y);
p[i].x=i;
v[i]=p[i].y;
}
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
dis[x][y]=min(dis[x][y],z);
dis[y][x]=min(dis[y][x],z);
}
sort(p+1,p+n+1);
for(int k=1;k<=n;k++){
int l=p[k].x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][l]+dis[l][j]);
ans[i][j]=min(ans[i][j],dis[i][j]+max(max(v[i],v[j]),v[l]));
}
}
}
for(int i=1;i<=K;i++){
int x,y;
scanf("%d %d",&x,&y);
printf("%d\n",ans[x][y]);
}
return 0;
}
评论 (0)
