很好的一道题，很神奇的算法，无向图最小环，inf开太大溢出wa~~~~无语
#include<iostream>
#define maxn 105
#define inf 1<<28
using namespace std;
int n,m;
int mapp[maxn][maxn];
int dp[maxn][maxn];
void init()
{
for(int i=0;i<maxn;i++)
{
for(int j=0;j<maxn;j++) mapp[i][j]=inf,dp[i][j]=inf;
}
}
void input()
{
for(int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
mapp[x][y]=mapp[y][x]=dp[x][y]=dp[y][x]=min(z,mapp[x][y]);
}
for(int i=1;i<=n;i++) mapp[i][i]=mapp[i][i]=dp[i][i]=dp[i][i]=0;
}
void flo()
{
int re=inf;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
re=min(re,dp[i][j]+mapp[j][k]+mapp[k][i]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
if(re==inf) cout<<"It's impossible."<<endl;
else cout<<re<<endl;
}
int main()
{
while(cin>>n>>m)
{
init();
input();
flo();
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
hdu 1599 find the mincost route
原文：http://blog.csdn.net/zafkiel_nightmare/article/details/48087471