Moving On Gym - 102222F

題意：

有 n 個城市，q 次詢問.

給出每個城市的危險度 r 和 城市的鄰接矩陣.

每次詢問給出 u、v、w，求從 u 到 v 且不經過其他危險度超過 w 的城市的最短路.

題解：

floyd 變形
我隊友一開始想的是每次加點然后跑dij，但是肯定會超時
我想的是給出起點和終點，選出滿足條件的城市，然后用這些城市去更新最短路徑
在本題中就是利用floyd來做，一半來說第三層循環是枚舉中間變量k，我們將其提到最外面，對于每一次詢問，都有一個危險值上限w，我們根據這個w，篩選出危險值小于w的所有點（即城市），然后依次跑更新操作，等全部跑完，此時詢問的兩個城市之間的路徑長度即為最短路且所有城市危險值不會超過w
方法二：
我還看到一個做法，
dp[k][i][j]表示最大權值為所有權值k大的i到j的最短路距離
對城市的危險值排序，依次加點更新不同層次的最短路
最后讀入直接輸出
我感覺兩個方法本質應該差不多

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=300; const int maxm=2e4+9; int dis[maxn][maxn]; struct node{int u,v,w;int id; }qq[maxm]; struct nod {int id,r; }a[maxn]; int ans[maxm]; bool cmp(node a,node b) {return a.w<b.w; } bool cmp1(nod a,nod b) {return a.r<b.r; } int main() {int t;cin>>t;for(int tt=1;tt<=t;tt++){//memset(dis,0x3f,sizeof dis);//memset(ans,0,sizeof ans);int n,q;scanf("%d%d",&n,&q);//cin>>n>>q;for(int i=1;i<=n;i++){scanf("%d",&a[i].r);//cin>>a[i].r;a[i].id=i;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&dis[i][j]);//cin>>dis[i][j];}}for(int i=1;i<=q;i++){int u,v,w;scanf("%d%d%d",&qq[i].u,&qq[i].v,&qq[i].w);//cin>>qq[i].u>>qq[i].v>>qq[i].w;qq[i].id=i;}sort(qq+1,qq+1+q,cmp);sort(a+1,a+1+n,cmp1);int cur=1;for(int xx=1;xx<=q;xx++)//q*n*n*?n{while(a[cur].r<=qq[xx].w&&cur<=n){int k=a[cur].id;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);}}cur++;}ans[qq[xx].id]=dis[qq[xx].u][qq[xx].v];} // for(int i=1;i<=n;i++) // { // // for(int j=i;j<=n;j++) // { // if(i==j) // { // dis[i][j]=0; // dis[j][i]=0; // } // for(int k=1;k<=n;k++){ // //if() // dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); // } // } // } printf("Case #%d:\n",tt);for(int i=1;i<=q;i++){cout<<ans[i]<<endl;}}return 0;}

第二個方法：

#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> using namespace std; int dp[310][310][310]; int has[310];int dan[310];int num[310];bool cmp(int a,int b){return dan[a]<dan[b]; }int main(){int t;int cur=1;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);memset(dp,0x3f3f3f3f,sizeof(dp));int cnt=1;for(int i=1;i<=n;i++){scanf("%d",&dan[i]);num[i]=i;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&dp[i][j][0]);sort(num+1,num+1+n,cmp);for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j][k]=min(dp[i][j][k-1],dp[i][num[k]][k-1]+dp[num[k]][j][k-1]);}}}printf("Case #%d:\n",cur++);while(m--){int st,ed,w;scanf("%d%d%d",&st,&ed,&w);int ans=0;for(int i=1;i<=n;i++){if(dan[num[i]]<=w) ans=i;}printf("%d\n",dp[st][ed][ans]);}} }

總結

以上是生活随笔為你收集整理的Moving On Gym - 102222F的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。