HDU 1599 find the mincost route

Floyd可解。

求最短。在路上來回。使用Floyd 而在 三同時不 找出最短。然后更新。

沒有推理啟動！=INF。

一堆負面結果溢出。

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int g[101][101],n,m;
int dis[101][101];
int ans;
int Floyd()
{for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=g[i][j];for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j&&j!=k&&i!=k&&g[i][k]!=INF&&g[k][j]!=INF&&dis[i][j]!=INF)ans=min(ans,dis[i][j]+g[i][k]+g[k][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(dis[i][k]!=INF&&dis[k][j]!=INF)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}}if(ans==INF)puts("It's impossible.");elseprintf("%d\n",ans);
}int main()
{while(scanf("%d%d",&n,&m)!=EOF){int u,v,len;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)g[i][j]=0;else g[i][j]=INF;}for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&len);g[u][v]=min(g[u][v],len);g[v][u]=min(g[u][v],len);}ans=INF;Floyd();}
}

版權聲明：本文博客原創文章。博客，未經同意，不得轉載。