三行floyd也是很神奇的東西（大霧
vijos1942
題目大概就是在線添加邊。。

之前做過(guò)一道差不多的題，是不斷加點(diǎn)的。。

然而這道題是不斷加邊

其實(shí)dij啊spfa的都可以，甚至比f(wàn)loyd快

然而floyd能過(guò)的題為什么去寫別的（滑稽

這里做一些小變動(dòng)，原先我們的floyd是枚舉中間點(diǎn)，而這里我們用枚舉中間邊
不過(guò)其實(shí)。。直接拿兩個(gè)端點(diǎn)去更新一遍好像也是可以的

if(kind==1){scanf("%d%d%d",&x,&y,&z);if(z<f[x][y]) {f[x][y]=f[y][x]=z;For(i,1,n)For(j,1,n)f[i][j]=f[j][i]=min(f[i][j],f[i][x]+f[y][j]+f[x][y]);}}

這里注意，因?yàn)閒數(shù)組顯然是對(duì)稱的，但是x,y是有序的，所以f[i][j]更新后f[j][i]不一定可以被更新到

然后就是道水題了

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<string> #include<map> #include<cstring> #include<vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(ll i=j;i<=k;i++) #define Dow(i,j,k) for(ll i=k;i>=j;i--) using namespace std; int f[101][101],n,m,kind,x,y,z; int main() {scanf("%d%d",&n,&m);For(i,1,n) For(j,1,n) f[i][j]=1e9;For(i,1,n) f[i][i]=0;For(i,1,m){scanf("%d",&kind);if(kind==1){scanf("%d%d%d",&x,&y,&z);if(z<f[x][y]) {f[x][y]=f[y][x]=z;For(i,1,n)For(j,1,n)f[i][j]=f[j][i]=min(f[i][j],f[i][x]+f[y][j]+f[x][y]);}}if(kind==0){scanf("%d%d",&x,&y);if(f[x][y]==1e9) puts("-1");else printf("%d\n",f[x][y]);}} }

枚舉端點(diǎn)AC代碼

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<string> #include<map> #include<cstring> #include<vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(ll i=j;i<=k;i++) #define Dow(i,j,k) for(ll i=k;i>=j;i--) using namespace std; int f[101][101],n,m,kind,x,y,z; int main() {scanf("%d%d",&n,&m);For(i,1,n) For(j,1,n) f[i][j]=1e9;For(i,1,n) f[i][i]=0;For(i,1,m){scanf("%d",&kind);if(kind==1){scanf("%d%d%d",&x,&y,&z);if(z<f[x][y]) {f[x][y]=f[y][x]=z;For(i,1,n)For(j,1,n)f[i][j]=min(f[i][j],f[i][x]+f[x][j]);For(i,1,n)For(j,1,n)f[i][j]=min(f[i][j],f[i][y]+f[y][j]);}}if(kind==0){scanf("%d%d",&x,&y);if(f[x][y]==1e9) puts("-1");else printf("%d\n",f[x][y]);}} }

總結(jié)

以上是生活随笔為你收集整理的vijos1942——小岛 Floyed的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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