floyed水题
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 #define INF 30000000 10 #define N 210 11 12 struct Node 13 { 14 int f,t,v; 15 int ans; 16 }e[N]; 17 18 int g[N][N]; 19 20 int n,m; 21 22 int main() 23 { 24 scanf("%d",&n); 25 for (int i=1;i<=n;i++) 26 for (int j=1;j<=n;j++) 27 scanf("%d",&g[i][j]); 28 scanf("%d",&m); 29 for (int i=1;i<=m;i++) 30 { 31 scanf("%d%d",&e[i].f,&e[i].t); 32 e[i].v=g[e[i].f][e[i].t]; 33 g[e[i].f][e[i].t]=INF; 34 } 35 for (int k=1;k<=n;k++) 36 for (int i=1;i<=n;i++) 37 for (int j=1;j<=n;j++) 38 g[i][j]=min(g[i][j],g[i][k]+g[k][j]); 39 for (int i=1;i<=n;i++) 40 for (int j=1;j<=n;j++) 41 e[m].ans+=g[i][j]; 42 for (int k=m;k>=1;k--) 43 { 44 for (int i=1;i<=n;i++) 45 for (int j=1;j<=n;j++) 46 g[i][j]=min(g[i][j],g[i][e[k].f]+g[e[k].t][j]+e[k].v); 47 for (int i=1;i<=n;i++) 48 for (int j=1;j<=n;j++) 49 e[k-1].ans+=g[i][j]; 50 } 51 for (int i=1;i<=m;i++) 52 if (e[i].ans>=INF) 53 printf("INF "); 54 else 55 printf("%d ",e[i].ans); 56 return 0; 57 }