图论--最短路径--观光旅游

短距离旅游

背景

湖南师大附中成为百年名校之后,每年要接待大批的游客前来参观,学校认为大力发展旅游业,可以带来一笔可观的收入。

输入格式

对于每组数据：

第一行有两个正整数N,M,分别表示学校的景点个数和有多少对景点之间直接有边相连,（N<=100,M<=10000）。

以下M行,每行三个正整数,分别表示一条道路的两端的编号,以及这条道路的长度。

输出格式

对于每组数据,输出一行：。

如果该回路存在,则输出一个正整数,表示该回路的总长度,否则输出“No solution.”（不要输出引号）。

样例1

样例输入1

5 7

1 4 1

1 3 300

3 1 10

1 2 16

2 3 100

2 5 15

5 3 20

4 3

1 2 10

1 3 20

1 4 30

样例输出1

61

No solution.这题一看就是典型的Flord最小环问题嘛。

这篇文章对Flord的讲解十分到位很适合新手/art/201403/433874.htm。

闲话少叙,代码走起

#include。

#include。

inline int min(int a,int b)。

{

return a

}

using namespace std;。

const int N=101;。

const int INF=999999;。

int dist[N][N],route[N][N];。

int n,m;

int main()。

{

int u,v,x;。

while(cin>>n>>m)。

{

memset(dist,0,sizeof(dist));。

for(int i=1;i<=n;i++)。

for(int j=1;j<=n;j++)。

dist[i][j]=route[i][j]=INF;。

for(int i=1;i<=m;i++)。

{

cin>>u>>v>>x;。

dist[u][v]=dist[v][u]=route[u][v]=route[v][u]=x;。

}

int ans=INF;。

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,route[i][j]+dist[i][k]+dist[k][j]);。

}

for(int i=1;i<=n;i++)。

for(int j=1;j<=n;j++)。

{

route[i][j]=min(route[i][j],route[i][k]+route[k][j]);。

}

}

if(ans==INF)。

cout<<'No solution.'<

else

cout<

}

return 0;

}