find the mincost route

杭州有N個景區，景區之間有一些雙向的路來連接，現在8600想找一條旅游路線，這個路線從A點出發并且最后回到A點，假設經過的路線為V1,V2,....VK,V1,那么必須滿足K>2,就是說至除了出發點以外至少要經過2個其他不同的景區，而且不能重復經過同一個景區。現在8600需要你幫他找一條這樣的路線，并且花費越少越好。?

Input

第一行是2個整數N和M（N <= 100, M <= 1000)，代表景區的個數和道路的條數。?
接下來的M行里，每行包括3個整數a,b,c.代表a和b之間有一條通路，并且需要花費c元(c <= 100)。

Output

對于每個測試實例，如果能找到這樣一條路線的話，輸出花費的最小值。如果找不到的話，輸出"It's impossible.".

Sample Input

3 3 1 2 1 2 3 1 1 3 1 3 3 1 2 1 1 2 3 2 3 1

Sample Output

3 It's impossible. #include <iostream> #include<string.h> #include<cstdio> #include <stack> #include <vector> using namespace std; #define INF 0x3f3f3f3f typedef long long ll; const int maxn=510; ll mp[maxn][maxn];//鄰接矩陣存圖 ll d[maxn][maxn];//保存兩點之間的最短距離 int n,m; ll MIN=INF; void floyd() {//一個環至少要3個互不相同的點，所以要保證k大于i，i大于jfor(int k=1;k<=n;k++){for(int i=1;i<k;i++)for(int j=i+1;j<k;j++)MIN=min(d[i][j]+mp[i][k]+mp[k][j],MIN);//得到從i出發，再回到i的最小環for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)//得到i,兩點的最短路徑d[i][j]=min(d[i][k]+d[k][j],d[i][j]);} } int main() {while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j)mp[i][j]=d[i][j]=0;else mp[i][j]=d[j][i]=INF;MIN=INF;for(int i=0;i<m;i++){ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);mp[u][v]=mp[v][u]=min(mp[u][v],w);d[u][v]=d[v][u]=mp[u][v];}floyd();if(MIN==INF)printf("It's impossible.\n");elseprintf("%lld\n",MIN);} }

無窮大 0x7ffffff?0x3f3f3f3f

#include <iostream> #include<string.h> #include<cstdio> #include <stack> #include <vector> using namespace std; #define INF 0x7ffffff const int maxn=510; int mp[maxn][maxn]; int d[maxn][maxn]; int n,m; int MIN=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++)MIN=min(d[i][j]+mp[i][k]+mp[k][j],MIN);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][k]+d[k][j],d[i][j]);} } int main() {while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j)mp[i][j]=d[i][j]=0;else mp[i][j]=d[j][i]=INF;MIN=INF;for(int i=0;i<m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);mp[u][v]=mp[v][u]=min(mp[u][v],w);d[u][v]=d[v][u]=mp[u][v];}floyd();if(MIN==INF)printf("It's impossible.\n");elseprintf("%d\n",MIN);} }

?

總結

以上是生活随笔為你收集整理的HDU1599 find the mincost route Floyd算法求最小环的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。