P2966 [USACO09DEC]牛收费路径Cow Toll Paths 题解

淩亂°似流年 2021-11-26 22:38 235阅读 0赞

# 一、题目： #

[洛谷原题][Link 1]

# 二、思路： #

此题可加深对Floyd的理解。

首先我们应该知道，Floyd中G\[i\]\[j\]实际上是一个滚动数组，真正的DP数组是G\[k\]\[i\]\[j\]，其中k是阶段.G\[k\]\[i\]\[j\]表示只经过\\(1 \\sim k\\)这些节点，i到j的最短距离。

那么如果我们还原这种DP状态，按照k的点权从小到大的顺序转移，那么我们询问的时候就只需要从1到n枚举最大点，用该点的点权加上i到j的最短路更新答案即可。

还有一个细节，注意到G\[i\]\[j\]保存的最短路不经过i和j本身，所以更新答案时注意用i的点权、j的点权与枚举的最大点的点权取max再加上最短路。

算法博大精深，切不可一知半解，如果不知道Floyd的本质，那这个题也就做不出来了。（这句话是留给我的。）

# 三、代码： #

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define FILEIN(s) freopen(s".in","r",stdin) #define FILEOUT(s) freopen(s".out","w",stdout) #define mem(s,v) memset(s,v,sizeof(s)) using namespace std; inline LL read(void){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } const int maxn=255; int n,m,q; int G[maxn][maxn][maxn]; int ref[maxn]; struct Weight{ int id,w; inline friend bool operator <(Weight x,Weight y){ return x.w<y.w; } }a[maxn]; int main(){ mem(G,0x3f); n=read();m=read();q=read(); for(register int i=1;i<=n;++i){ a[i].id=i; a[i].w=read(); G[i][i][0]=0; } sort(a+1,a+n+1); for(register int i=1;i<=n;++i){ ref[a[i].id]=i; } for(register int i=1;i<=m;++i){ int s=ref[read()],t=ref[read()],l=read(); G[t][s][0]=G[s][t][0]=min(G[s][t][0],l); } for(register int k=1;k<=n;++k){ for(register int i=1;i<=n;++i){ for(register int j=1;j<=n;++j){ G[i][j][k]=min(G[i][j][k],G[i][k][k-1]+G[k][j][k-1]); G[i][j][k]=min(G[i][j][k],G[i][j][k-1]); } } } for(register int step=1;step<=q;++step){ int s=ref[read()],t=ref[read()]; int minn=0x3f3f3f3f; for(register int i=1;i<=n;++i){ minn=min(minn,G[s][t][i]+max(max(a[s].w,a[t].w),a[i].w)); } printf("%d\n",minn); } return 0; }

转载于:https://www.cnblogs.com/little-aztl/p/11197475.html

[Link 1]: https://www.luogu.org/problemnew/show/P2966