首页 > 代码库 > 观光旅游

观光旅游

2024-08-14 16:24:13   218人阅读

【题目描述】

旅游区里有N个景点。两个景点之间可能存在长度为A的双向道路。

旅游区规定，每个游客的旅游线路只能是一个回路。小明来到这里旅游，希望尽量少走一些路，请你帮他求出最优路线长度。

【输入描述】

输入有多组数据，对于每组数据：

第一行输入两个正整数N、M，表示景点个数，以及有多少对景点之间存在道路(N ≤ 100，M ≤ 10000)；

接下来M行，每行输入三个正整数，表示一条道路的两端的景点编号，以及这条道路的长度( ≤ 1000)。

【输出描述】

对于每组数据，如果该回路存在，则输出一个正整数，表示该回路的总长度，否则输出“No solution.”。

【样例输入】

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

【样例输出】

61

No solution.

源代码：#include<cstdio>#include<algorithm>#define INF 1000000 //开大了竟然会爆。using namespace std;int m,n,ans,i[101][101],f[101][101];void Solve(){    ans=INF;    for (int a=1;a<=n;a++) //恶心的预处理。      for (int b=1;b<=n;b++)        f[a][b]=f[b][a]=i[a][b]=i[b][a]=a==b?0:INF;    for (int a=0;a<m;a++)    {        int t,t1,t2;        scanf("%d%d%d",&t1,&t2,&t);        f[t1][t2]=f[t2][t1]=i[t1][t2]=i[t2][t1]=t;    }    for (int a=1;a<=n;a++) //裸Floyd最小环。    {          for (int b=1;b<a;b++)            for (int c=b+1;c<a;c++)              ans=min(ans,i[b][c]+f[c][a]+f[a][b]);          for (int b=1;b<=n;b++)            for (int c=1;c<=n;c++)              i[b][c]=min(i[b][c],i[b][a]+i[a][c]);    }    if (ans==INF)      printf("No solution.\n");    else      printf("%d\n",ans);}int main(){    while (scanf("%d%d",&n,&m)==2)      Solve();    return 0;}/*    解题思路：        与Floyd相辅相成，第一层循环枚举中间点，那么中间点之前的点编号一定会比中间点的编号小。        设当前中间点为最小环中编号最大的点，易得，在使其更新最短路径前，所掌握的信息已完全包含了最小环。        易得，i[b][c]中没有中间点，故合法，即为：            Length=i[b][c]+f[c][a]+f[a][b]        定能找出最小环。*/

观光旅游


联系
我们