傳送門(mén)

解題思路

　　\(floyd\)的變形版，首先要求的是經(jīng)過(guò)的點(diǎn)中所有點(diǎn)最大的，那么我們就按照點(diǎn)權(quán)來(lái)排序。這樣的話(huà)每次我們枚舉的中轉(zhuǎn)點(diǎn)\(k\)是單調(diào)遞增的，所以每次的最大值一定是\(i,j,k\)其中一個(gè)。最好記兩個(gè)數(shù)組，一個(gè)帶點(diǎn)權(quán)一個(gè)不帶點(diǎn)權(quán)，這樣比較好寫(xiě)。

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm>using namespace std; const int MAXN = 255;inline int rd(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return f?x:-x; } int n,m,q,f[MAXN][MAXN],a[MAXN],g[MAXN][MAXN]; struct Data{int w,id; }data[MAXN];inline bool cmp(Data A,Data B){return A.w<B.w; }int main(){memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));n=rd();m=rd();q=rd();int x,y,z; for(int i=1;i<=n;i++) data[i].w=rd(),data[i].id=i,f[i][i]=0;sort(data+1,data+1+n,cmp);for(int i=1;i<=n;i++) a[data[i].id]=i;for(int i=1;i<=m;i++){x=rd(),y=rd(),z=rd();f[a[x]][a[y]]=f[a[y]][a[x]]=min(f[a[x]][a[y]],z);}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j) continue;f[i][j]=min(f[i][j],f[i][k]+f[k][j]);g[i][j]=min(g[i][j],f[i][j]+max(data[k].w,max(data[i].w,data[j].w)));} // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) cout<<a[i]<<" "<<a[j]<<" "<<g[a[i]][a[j]]<<endl;while(q--){x=rd(),y=rd(); printf("%d\n",g[a[x]][a[y]]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/sdfzsyq/p/9791695.html

總結(jié)

以上是生活随笔為你收集整理的LUOGU P2966 [USACO09DEC]牛收费路径Cow Toll Paths的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。