观光旅游 VIJOS-P1046 81分

#include <bits/stdc++.h>
#define INF 0x0fffffff
using namespace std;
const int N=110;
int n,m;
int f[N][N],a[N][N];
int ans=INF;
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<k;i++){
			for(int j=i+1;j<k;j++){
				ans=min(ans,f[i][j]+a[i][k]+a[k][j]);
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(i!=j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
}
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		ans=INF;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=INF;
				a[i][j]=INF;
			}
		}
		while(m--){
			int x,y,z;
			cin>>x>>y>>z;
			f[x][y]=min(z,f[x][y]);
			f[y][x]=min(z,f[y][x]);
			a[x][y]=min(z,a[x][y]);
			a[y][x]=min(z,a[y][x]);
		}
		floyd();
		if(ans<INF){
			cout<<ans<<endl;
		}
		else{
			cout<<"No solution."<<endl;
		}
	}
	return 0;
}