旅行社的烦恼-白红宇的个人博客

旅行社的烦恼

发布日期：2022-02-02 02:58:05 浏览次数：13 分类：技术文章

本文共 2175 字，大约阅读时间需要 7 分钟。

Description

V11开了一家旅行社，众所周知现在商业竞争越来越激烈，为了更好地吸引消费者的眼球，v11决定制定到一条最短的旅游路线，路线的开始点和结束点必须是同一个地方。你的任务就是编写程序帮助v11寻找到这样的路线。

现在给出旅行路线图，图中有N个景点编号从1到N，有M条双向边编号从1到M。每条边包含三个数字A,B,C。表示这条路线连接景点A和景点B，他们之间的距离是C。为了简化问题，我们认为：每条旅游路线是一个至少包含三个点的简单回路。每条旅游路线的长度为它包含的所有边的距离之和。

现在的任务是：要求你编写程序寻找这样的最短路，给出它的路程长度，并输出同时存在有几个这样的最短路。

注意的是：

1.当两条最短路程中所经过的景点（不考虑顺序），完全相同时，才是相同的最短路程。否则，算作不同的最短路程。

2. 图的顶点序列中，除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路。（本题中将第一个顶点和最后一个顶点当作同一个景点）

3.本题中不存在自环。

Input

输入数据第一行包含一个整数T，表示测试数据的组数。对于每组测试数据：

第一行为两个整数n,m(1<n<100,1<m<5000)，接下来m行，每行三个整数a,b,v(1<=a,b<=n,1<v<500)，表示第i条路线连接景点A和景点B，距离是V。两个数字之间用空格隔开。

Output

对于每组测试数据：如果存在这样的最短路线，输出它的长度和不同的最短路线的个数。如果不存在则输出-1。两个数字之间用空格隔开，每组测试数据一行。

Sample Input

13 31 2 13 1 13 2 1

Sample Output

3 1

Hint

样例一中，我们可以从景点1出发的路线：1->2->3->1;

可以从景点2出发的路线：2->3->1->2;

同样也可以从景点3出发的路线:3->1->2->3;

我们认为这3条路线所经过的景点集合为{1,2,3}所以他们是相同的路线。

代码：

#include
   
    #include
    
     #define M 107#define inf 0x3f3f3fusing namespace std;int g[M][M],dis[M][M],path[M][M],pre[M];int n,m,num,mincircle,count;void init(){    for(int i=1; i<=n; i++)    {        for(int j=1; j<=n; j++)        {            g[i][j]=dis[i][j]=inf;        }        g[i][i]=dis[i][i]=0;    }}void dfs(int i,int j){    int k=path[i][j];    if(k==0)    {        pre[num++]=j;        return ;    }    dfs(i,k);    dfs(k,j);}void Floyd(){    mincircle=inf;    for(int k=1; k<=n; k++)    {        for(int i=1; i
     
      dis[i][j]+g[i][k]+g[k][j])                {                    mincircle=dis[i][j]+g[i][k]+g[k][j];                    num=0;                    pre[num++]=i;                    dfs(i,j);                    pre[num++]=k;                    count=1;                }                else if(mincircle==dis[i][j]+g[i][k]+g[k][j])//记录次数                    count++;            }        for(int i=1; i<=n; i++)//求最短路            for(int j=1; j<=n; j++)                if(dis[i][k]+dis[k][j]
      
       c)            {                g[a][b]=g[b][a]=c;                dis[a][b]=dis[b][a]=c;            }        }        memset(path,0,sizeof(path));        Floyd();        if(mincircle==inf)            printf("-1\n");        else            printf("%d %d\n",mincircle,count);    }    return 0;}

转载地址：https://blog.csdn.net/u010368749/article/details/14139911 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：播放器

下一篇：hdu-1011

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章