題目鏈接：點擊查看

題目大意：給出一個圖，包括n個點和m條邊，然后給出6個查詢，每次詢問給出兩個點u和v，輸出v到u的最短路的相反數，并將u到v，權值為剛才求出的答案這條邊加入到圖中

題目分析：裸的最短路，不過有負邊權，但是n很小，只有300，用spfa或floyd都可以，當時比賽的時候愣是沒讀懂題目是什么意思，題目整的花里胡哨的。。也是服了，不過用floyd的時候注意一下，每次重新跑最短路的時候要從初始狀態跑，不能從上一次跑完的的矩陣再跑，開個輔助數組保存一下一開始的邊權即可，剩下的就是模板題了，倆方法都寫了一遍，直接上代碼吧：

SPFA：

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long LL;const int inf=0x3f3f3f3f;const int N=310;int n,m;int d[N];bool vis[N];int maze[N][N];void spfa(int u) {memset(d,inf,sizeof(d));memset(vis,false,sizeof(vis));d[u]=0;vis[u]=true;queue<int>q;q.push(u);while(!q.empty()){int temp=q.front();q.pop();vis[temp]=false;for(int i=1;i<=n;i++){if(maze[temp][i]==inf)continue;if(d[i]>d[temp]+maze[temp][i]){d[i]=d[temp]+maze[temp][i];if(!vis[i]){q.push(i);vis[i]=true;}}}} }int main() {int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)maze[i][j]=i==j?0:inf;while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);u++;v++;maze[u][v]=w;}for(int i=1;i<=6;i++){int u,v;scanf("%d%d",&u,&v);u++;v++;spfa(v);printf("%d\n",-d[u]);maze[u][v]=-d[u];}} return 0; }

Floyd：?

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long LL;const int inf=0x3f3f3f3f;const int N=310;int n,m;int maze[N][N];int main() {int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)maze[i][j]=i==j?0:inf;while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);u++;v++;maze[u][v]=w;}for(int t=1;t<=6;t++){int u,v;scanf("%d%d",&u,&v);u++;v++;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){if(maze[i][k]==inf)continue;for(int j=1;j<=n;j++){if(maze[i][j]>maze[i][k]+maze[k][j])maze[i][j]=maze[i][k]+maze[k][j];}}}printf("%d\n",-maze[v][u]);maze[u][v]=-maze[v][u];}} return 0; }

?

總結

以上是生活随笔為你收集整理的2019ICPC(南京) - Holy Grail(最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

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