Description

　　在桑給巴爾島的Adelton城鎮(zhèn)上有一個旅游機(jī)構(gòu)。它們決定在提供許多的其它吸引之外，再向客人們提供旅游本鎮(zhèn)的服務(wù)。 為了從提供的吸引服務(wù)中盡可能地獲利，這個旅游機(jī)構(gòu)接收了一個精明決定：在相同的起點與終點之間找出一最短路線。

Input

　　你的任務(wù)是編寫一條程序來找類似的的一條路線。在這個鎮(zhèn)上，有N個十字路口(編號1至N)，兩個十字路口之間可以有多條道路連接，有M條道路（編號為1至M)。但沒有一條道路從一個十字路口出發(fā)又回到同一個路口。每一條觀光路線都是由一些路組成的，這些道路序號是：y1, …, yk,且k>2。第yi(1<=i<=k-1)號路是連接第xi號十字路口和第x［i+1］號十字路口的；其中第yk號路是連接第xk號十字路口和第x[k+1]號十字路口。而且所有的這些x1,…,xk分別代表不同路口的序號。在某一條觀光路線上所有道路的長度的和就是這條觀光路線的總長度。換言之L(y1)+L(y2)+…+L(yk)的和, L(yi)就是第yi號觀光路線的長度。你的程序必須找出類似的一條路線：長度必須最小，或者說明在這個城鎮(zhèn)上不存在這條觀光路線。

Output

每組數(shù)據(jù)的第一行包含兩個正整數(shù)：十字路口的個數(shù)N(N<=100)，另一個是道路的 數(shù)目M(M<10000)。接下來的每一行描述一條路：每一行有三個正整數(shù)：這條路連接的兩個路口的編號，以及這條路的長度（小于500的正整數(shù)）。

Sample Input

　　每一行輸出都是一個答案。如果這條觀光路線是不存在的話就顯示“No solution”；或者輸出這條最短路線的長度。

Sample Output

樣例１
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

樣例2
4 3
1 2 10
1 3 20
1 4 30
-1

Hint

樣例１
61

樣例2
No solution
.
.
.
.
.
.

分析

因為Floyd的枚舉順序，我們可以肯定，最短路必定是1~k-1的所有最短路
然后我們把k移到外面，然后以k作為中間點，枚舉i，j，都為與k相連的點，那么因為k還沒進(jìn)入最短路圖中，所以i，j間的最短路即為最小環(huán)減去mapi,k,mapk,j的權(quán)值的數(shù)，所以再加上這兩條邊，然后記錄所得的最小值，就是最小環(huán)了
.
.
.
.
.

程序：

#include <iostream> #include <cstdio> using namespace std; int n,m; int a[101][101],f[101][101]; int b[101],d[101]; int main() {int u,v,w;int max=111111117;int ans=max;cin>>n>>m;for (int i=1;i<=100;i++)for (int j=1;j<=100;j++){a[i][j]=max;f[i][j]=max;}for (int i=1;i<=m;i++){cin>>u>>v;cin>>w;a[u][v]=w;f[u][v]=a[u][v];a[v][u]=w;f[v][u]=a[v][u];}for (int k=1;k<=n;k++){for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++)ans=min(ans,f[i][j]+a[j][k]+a[k][i]);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);}if (ans!=max) cout<<ans;else cout<<"No solution";return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499958.html

總結(jié)

以上是生活随笔為你收集整理的观光旅游(Floyd)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。