开启左侧

大臣的旅费

二维码 [复制链接]
237 0
很久以前,T王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。

为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋,用于存放往来城市间的路费。

聪明的J发现,如果不在某个城市停下来修整,在连续行进过程中,他所花的路费与他已走过的距离有关,在走第x千米到第x+1千米这一千米中(x是整数),他花费的路费是x+10这么多。也就是说走1千米花费11,走2千米要花费23。

J大臣想知道:他从某一个城市出发,中间不休息,到达另一个城市,所有可能花费的路费中最多是多少呢?

输入格式:
输入的第一行包含一个整数n,表示包括首都在内的T王国的城市数
城市从1开始依次编号,1号城市为首都。
接下来n-1行,描述T国的高速路(T国的高速路一定是n-1条)
每行三个整数Pi, Qi, Di,表示城市Pi和城市Qi之间有一条高速路,长度为Di千米。

输出格式:
输出一个整数,表示大臣J最多花费的路费是多少。

样例输入:
5
1 2 2
1 3 1
2 4 5
2 5 4

样例输出:
135

样例说明:
大臣J从城市4到城市5要花费135的路费。

资源约定:
峰值内存消耗 < 64M
CPU消耗  < 5000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。

参考答案:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. // 调试开关
  5. #define _DEBUG_ 0

  6. // 最大顶点个数
  7. #define MAX_VERTEX 32

  8. // 取最大值
  9. #define MAX(a, b) ((a) > (b) ? (a) : (b))

  10. // 检测分配内存是否成功
  11. #define CHECK_MALLOC(p)               \
  12. {                                     \
  13.     if (NULL == p)                    \
  14.     {                                 \
  15.         printf("malloc error.\n");    \
  16.         return -1;                    \
  17.     }                                 \
  18. }

  19. // 邻接点结构定义
  20. typedef struct EdgeNode
  21. {
  22.     int adjVex;              // 邻接点在顶点表中的下标
  23.     int weight;              // 权值,这里指距离
  24.    
  25.     struct EdgeNode *next;   // 下一个邻接点
  26. }EdgeNode;

  27. // 顶点表结点定义
  28. typedef struct
  29. {
  30.     int index;               // 城市编号
  31.     EdgeNode *firstEdge;     // 第一个邻接点
  32. }AdjList[MAX_VERTEX];

  33. // 邻接表结构定义
  34. typedef struct
  35. {
  36.     int vertexNum;            // 顶点数
  37.     int edgeNum;              // 边数
  38.     AdjList adjList;          // 邻接表
  39. }GraphAdjList;

  40. // -------------------------------------------------------------------------
  41. // - 函 数 名: initAdjList
  42. // - 功能描述: 初始化邻接表
  43. // - 输入参数: vertexNum:顶点个数;edgeNum:边数
  44. // - 输出参数: graph:邻接图
  45. // - 返 回 值: void
  46. // - 备    注:
  47. // -------------------------------------------------------------------------
  48. void initAdjList(GraphAdjList *graph, int vertexNum, int edgeNum)
  49. {
  50.     int i;
  51.    
  52.     memset(graph, 0, sizeof(GraphAdjList));
  53.    
  54.     graph->vertexNum = vertexNum;
  55.     graph->edgeNum = edgeNum;
  56.    
  57.     for (i = 0; i < graph->vertexNum; i++)
  58.     {
  59.         graph->adjList[i].index = i;
  60.         graph->adjList[i].firstEdge = NULL;
  61.     }
  62. }

  63. // -------------------------------------------------------------------------
  64. // - 函 数 名: createAdjList
  65. // - 功能描述: 创建邻接表
  66. // - 输入参数: 无
  67. // - 输出参数: graph:邻接图
  68. // - 返 回 值: 0:成功;其他:失败
  69. // - 备    注:
  70. // -------------------------------------------------------------------------
  71. int createAdjList(GraphAdjList *graph)
  72. {
  73.     int i;                          // 循环变量
  74.     int from;                       // 起始城市编号
  75.     int to;                         // 目标城市编号
  76.     int distance;                   // 两城市间距离
  77.     EdgeNode *pEdgeNode = NULL;
  78.    
  79.     for (i = 0; i < graph->edgeNum; i++)
  80.     {
  81.         // 从标准输入获取高速公路信息
  82.         fflush(stdin);
  83.         scanf("%d %d %d", &from, &to, &distance);

  84.         // 将高速公路信息加入邻接表
  85.         pEdgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
  86.         CHECK_MALLOC(pEdgeNode);
  87.         pEdgeNode->adjVex = to - 1;
  88.         pEdgeNode->weight = distance;
  89.         pEdgeNode->next = graph->adjList[from-1].firstEdge;
  90.         graph->adjList[from-1].firstEdge = pEdgeNode;
  91.         
  92.         pEdgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
  93.         CHECK_MALLOC(pEdgeNode);
  94.         pEdgeNode->adjVex = from - 1;
  95.         pEdgeNode->weight = distance;
  96.         pEdgeNode->next = graph->adjList[to-1].firstEdge;
  97.         graph->adjList[to-1].firstEdge = pEdgeNode;
  98.     }
  99.    
  100.     return 0;
  101. }

  102. #if _DEBUG_
  103. // -------------------------------------------------------------------------
  104. // - 函 数 名: printGraphAdjList
  105. // - 功能描述: 打印邻接表
  106. // - 输入参数: graph:邻接表指针
  107. // - 输出参数: 无
  108. // - 返 回 值: void
  109. // - 备    注: 调试使用,格式为:"[城市编号]: ->(相邻城市编号,距离)"
  110. // -------------------------------------------------------------------------
  111. void printGraphAdjList(const GraphAdjList *graph)
  112. {
  113.     int i;
  114.     EdgeNode *pEdgeNode = NULL;
  115.    
  116.     puts("=========================");
  117.     for (i = 0; i < graph->vertexNum; i++)
  118.     {
  119.         printf("[%d]: ", graph->adjList[i].index);
  120.         
  121.         pEdgeNode = graph->adjList[i].firstEdge;
  122.         while (NULL != pEdgeNode)
  123.         {
  124.             printf("->(%d,%d)", pEdgeNode->adjVex + 1, pEdgeNode->weight + 1);
  125.             pEdgeNode = pEdgeNode->next;
  126.         }
  127.         
  128.         printf("\n");
  129.     }
  130.     puts("=========================");
  131. }
  132. #endif

  133. // -------------------------------------------------------------------------
  134. // - 函 数 名: dfs
  135. // - 功能描述: 深度优先遍历邻接图
  136. // - 输入参数: graph:邻接图指针;vertex1:起始城市编号;vertex2:目标城市编号
  137. // - 输出参数: distance:两城市之间距离;visit:访问标记
  138. // - 返 回 值: 0:成功;1:失败
  139. // - 备    注:
  140. // -------------------------------------------------------------------------
  141. int dfs(GraphAdjList *graph, int vertex1, int vertex2, int *distance, int visit[])
  142. {
  143.     EdgeNode *pEdgeNode = NULL;

  144.     // 之前已经访问过,回退
  145.     if (0 != visit[vertex1])
  146.     {
  147.         return 1;
  148.     }

  149.     // 打访问标记
  150.     visit[vertex1] = 1;

  151.     // 找到目标城市,返回成功
  152.     if (graph->adjList[vertex1].index == vertex2)
  153.     {
  154.         return 0;
  155.     }

  156.     // 遍历当前城市的所有邻接城市
  157.     pEdgeNode = graph->adjList[vertex1].firstEdge;
  158.     while (NULL != pEdgeNode)
  159.     {
  160.         // 没访问过则访问
  161.         if (0 == visit[pEdgeNode->adjVex])
  162.         {
  163.             // 加上与当前城市之间的距离
  164.             *distance += pEdgeNode->weight;

  165.             // 递归访问城市
  166.             if (0 == dfs(graph, pEdgeNode->adjVex, vertex2, distance, visit))
  167.             {
  168.                 return 0;
  169.             }
  170.         }

  171.         pEdgeNode = pEdgeNode->next;
  172.     }

  173.     // 在当前城市的所有邻接城市中均未找到目标城市,减去距离,回退
  174.     *distance -= graph->adjList[vertex1].firstEdge->weight;

  175.     return 1;
  176. }

  177. // -------------------------------------------------------------------------
  178. // - 函 数 名: getDistance
  179. // - 功能描述: 获取两城市之间的距离
  180. // - 输入参数: graph:邻接图;vertex1:城市1下标;vertex2:城市2下标
  181. // - 输出参数: 无
  182. // - 返 回 值: int 两城市之间的距离
  183. // - 备    注:
  184. // -------------------------------------------------------------------------
  185. int getDistance(GraphAdjList *graph, int vertex1, int vertex2)
  186. {
  187.     int distance = 0;                 // 城市距离
  188.     int visited[MAX_VERTEX] = {0};    // 访问标记

  189.     (void)dfs(graph, vertex1, vertex2, &distance, visited);

  190.     return distance;
  191. }

  192. // -------------------------------------------------------------------------
  193. // - 函 数 名: getMaxDistance
  194. // - 功能描述: 获取图中最远的两座城市之间的距离
  195. // - 输入参数: graph:邻接图
  196. // - 输出参数: 无
  197. // - 返 回 值: int 最大距离
  198. // - 备    注:
  199. // -------------------------------------------------------------------------
  200. int getMaxDistance(GraphAdjList *graph)
  201. {
  202.     int maxDistance = 0;
  203.     int tmpDistance;
  204.     int i, j;

  205.     // 计算各对城市之间的距离,取最大值
  206.     for (i = 0; i < graph->vertexNum; i++)
  207.     {
  208.         for (j = i + 1; j < graph->vertexNum; j++)
  209.         {
  210.             tmpDistance = getDistance(graph, i, j);

  211. #if _DEBUG_
  212.             printf("(%d,%d): %d\n", i + 1, j + 1, tmpDistance);
  213. #endif

  214.             maxDistance = MAX(tmpDistance, maxDistance);
  215.         }
  216.     }

  217.     return maxDistance;
  218. }

  219. // -------------------------------------------------------------------------
  220. // - 函 数 名: calcFee
  221. // - 功能描述: 根据距离计算路费
  222. // - 输入参数: distance:距离
  223. // - 输出参数: 无
  224. // - 返 回 值: int:路费
  225. // - 备    注:
  226. // -------------------------------------------------------------------------
  227. int calcFee(int distance)
  228. {
  229.     return (10 * distance + distance * (distance + 1) / 2);
  230. }

  231. int main()
  232. {
  233.     int cityNum;               // 城市数
  234.     int maxDistance = 0;       // 城市间最大距离
  235.     GraphAdjList graph;        // 邻接图

  236.     scanf("%d", &cityNum);
  237.    
  238.     // 初始化邻接表
  239.     initAdjList(&graph, cityNum, cityNum - 1);
  240.    
  241.     // 建立边表
  242.     if (0 != createAdjList(&graph))
  243.     {
  244.         printf("create graph failed.\n");
  245.         return -1;
  246.     }

  247. #if _DEBUG_
  248.     // 打印邻接表
  249.     printGraphAdjList(&graph);
  250. #endif

  251.     // 遍历邻接表寻找最远的两座城市
  252.     maxDistance = getMaxDistance(&graph);

  253.     // 计算并打印最多的路费
  254.     printf("%d\n", calcFee(maxDistance));
  255.    
  256.     return 0;
  257. }
复制代码



赞助本站





上一篇:买不到的数目
下一篇:剪格子
学会善用【论坛搜索】功能,很多你要寻找的答案就在这里面;
资源共享区【解压密码】集合,【爱好街币】的作用与获取方式;
您需要登录后才可以回帖 登录 | 注册

本版积分规则

发新帖 回复

104

主题

104

帖子

233

街币
更多

精彩推荐

爱好街资源共享区文件解压密码
爱好街资源共享区文件解压密码
因本站分享的文件实在太多,目前收集整理已经接近4T,所以有些文
新人报到专用贴
新人报到专用贴
==新人报道格式(选填)== 【我的昵称】: 【我的性别
易辅客栈VIP教程之从零学辅助系列(大漠主讲)
易辅客栈VIP教程之从零学辅助
学易语言的都知道大漠,而且这套教材是零基础入门,非常棒的
独立团VIP教程第1-7版全套打包下载(含课件源码工具等)
独立团VIP教程第1-7版全套打包
独立团第1版易语言教程 独立团第一版1易语言入门 1-1-1外
挂茶馆全套教程(含课件,源码,工具等)完整版下载
挂茶馆全套教程(含课件,源码,
一切从零开始教程目录 第一部(游戏为征途,随便
爱好街链接地址失效有奖报错
爱好街链接地址失效有奖报错
我们的成长离不开大家的支持!! 各位爱好街的会员:

免责声明:
在爱好街发布的文章与主题属会员个人意见,与本站立场无关,文章内容由作者与爱好街享有相关版权,如需转载请注明出处或取得会员与本站的许可,否则本站将追究相应的法律责任,如部分内容有侵犯任何版权问题,请立即告知本站,本站将及时予以删除并致以最深的歉意。另外不得将本站内容用于商业或者非法用途,否则,一切后果请用户自负。

Mail To:MasTer@AiHaiJie.Com

快速回复
快速回复 返回顶部 返回列表