P2966 [USACO09DEC] Cow Toll Paths G 题解
题目链接
我的博客
思路
首先看数据范围。发现 \(1 \leq n \leq 250\)，此题还是一个最短路问题，因此考虑Floyd算法。
但是这道题不仅仅涉及到边权，还有点权，并且要求点权最大的最小值。因此我们可以按照点权从小到大排序来跑Floyd。
\[dis_{i,j}=\min \{ dis_{i,k}+dis_{k,j} \}
\]
最终的答案就是
\[ans_{i,j}= \min \{dis_{i,j}+\max\{val_i,val_j,val_k \} \}
\]
注意：按照点权排序后的点的编号与之前不同，因此要将上文中的 \(i,j,k\) 改为 \(id_i,id_j,id_k\)。
时间复杂度 \(O(n^3)\)。
如果你发现你按照以上方法仅仅获得 \(50pts\) 的好成绩，恭喜你！
可能有重边，但保证无自环。
所以你需要处理重边，即每次输入的时候 \(dis_{u,v}=\min ( dis_{u,v},w)\)。
代码
const int N=250+10;
int n,m,q;
int dis[N][N],ans[N][N];
//dis：表示最短路的距离
//ans：表示答案
struct node{int id,w;//id：点的编号，w：点权
}c[N];
bool cmp(node A,node B){return A.w<B.w;}//按照点权从小到大排序
signed main(){n=Read();m=Read();q=Read();for(int i=1;i<=n;i++){c[i].w=Read();c[i].id=i;}for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=INF,ans[i][j]=INF;//初始化for(int i=1;i<=n;i++) dis[i][i]=0;//自己到自己为 0while(m--){int u=Read(),v=Read(),w=Read();dis[u][v]=dis[v][u]=min(dis[u][v],w);//处理重边！}sort(c+1,c+n+1,cmp);for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[c[i].id][c[j].id]=min(dis[c[i].id][c[j].id],dis[c[i].id][c[k].id]+dis[c[k].id][c[j].id]);//同上文ans[c[i].id][c[j].id]=min(ans[c[i].id][c[j].id],dis[c[i].id][c[j].id]+max(max(c[i].w,c[j].w),c[k].w));}}} while(q--){int s=Read(),t=Read();printf("%d\n",ans[s][t]);}return 0;
}