[洛谷]P6464 [传智杯 #2 决赛] 传送门

看到数据范围：n<=100，嗯......脑子闪过：还在想什么呢！Floyd啊。哈哈哈

思路：

详细注释：

话不多说，上ACcode！:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e9+10
const int N=1e2+10;
int n,m,f[N][N],g[N][N],ans=inf;//结果;//f:原数组备份
void floyd() {//先跑一遍 正常的floyedfor(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++) {g[i][j]=min(g[i][j],g[i][k]+g[k][j]);f[i][j]=g[i][j];}
}void floyd1(int k) { //就k为中转点，跑floyd for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}int sum() {//求和，所用点路径和 int res=0;for(int i=1; i<=n; i++) {for(int j=1; j<i; j++) {res+=g[i][j];}}return res;
}void init() {//恢复图 for(int i=1; i<=n; i++)for(int j=1; j<=n; j++) {g[i][j]=f[i][j];}
}
void init1() {//初始化地图 for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(i!=j) g[i][j]=inf;
}
void solve() {cin>>n>>m;init1();for(int i=1; i<=m; i++) { //建图int u,v,w;cin>>u>>v>>w;g[u][v]=g[v][u]=w;}floyd();//先跑一边floyd,因为后面都是单独点做中转点,不然每次都跑//全部点中转，会超时 //但是把两个点之间的距离降为零，跑floyd求最短路是要全部点做中转点//才行 //我们先把所用点都可以当作中转点求一下最短路//后面把两两之间的路降为零，最短路只会更小，不受影响 for(int i=1; i<=n; i++) {//枚举每两个点之间的传送门 for(int j=1; j<i; j++) {g[i][j]=g[j][i]=0;//i,j传送门开启floyd1(i);//就是用前两层循环的参数i，j当作中转点//这样就可以省去枚举中转点 k的时间了。这样子就是O（n2） floyd1(j);ans=min(ans,sum()); //求和的最小数 init();//恢复数组，因为每次都是独立的 }}cout<<ans<<"\n";//结果 
}
signed  main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int tt=1;//cin>>tt;while(tt--) {solve();}return 0;
}

over~