#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=1e8;
int n,m,a[N][N],f[N][N],ans=inf;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
fs(i,1,n,1){
fs(j,1,n,1){
if(i-j){
a[i][j]=f[i][j]=inf;
}
}
}
fs(i,1,m,1){
int u,v,w;
cin>>u>>v>>w;
a[u][v]=f[u][v]=w;
a[v][u]=f[v][u]=w;
}
fs(k,1,n,1){
fs(i,1,k-1,1){
fs(j,i+1,k-1,1){
if(ans>f[i][j]+a[i][k]+a[k][j]){
ans=f[i][j]+a[i][k]+a[k][j];
}
}
}
fs(i,1,n,1){
fs(j,1,n,1){
if(f[i][j]>f[i][k]+f[k][j]){
f[i][j]=f[i][k]+f[k][j];
}
f[j][i]=f[i][j];
}
}
}
if(ans>=inf){
cout<<"No solution.";
}else{
cout<<ans;
}
return 0;
}
最小环代码
发布于
2020-07-29
|
2分钟
|
272字数
- 本文作者: Billy2007&GoneTimeの世界
- 本文链接: 最小环代码
- 版权声明: 本博客所有文章除特别声明外,转载请注明出处!
0%
召唤伊斯特瓦尔