鱼C论坛

 找回密码
 立即注册
查看: 2344|回复: 0

[技术交流] PAT练习笔记——1003. Emergency (25)

[复制链接]
发表于 2017-7-13 22:10:01 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
1003. Emergency (25)
时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Input
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) - the number of cities (and the cities are numbered from 0 to N-1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
Output
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
Sample Input
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output
2 4
思路:
最短路径问题,需要遍历所有的路径进行搜索,再计算最短路径以及最大拥有的队伍数目。
问题优化:可以先用Dijkstra算最短路径,再深度优先遍历所有路径(并不是所有的点,是路径),筛选获得需要的结果路径
(图的说明可参考小甲鱼数据结构54讲至61讲)
不知道是不是还有更好的方法?求指教。
  1. #include<stdio.h>

  2. #define MAX_VERTEX_NUM 500 /*邻阶矩阵最大顶点数*/
  3. #define Inf 65535/*表示无穷大*/

  4. typedef struct ArcNode{
  5.         int length;/*权值*/
  6. }ArcNode;/*边*/

  7. typedef struct AdjMatrix{
  8.         int vertex[MAX_VERTEX_NUM];
  9.         ArcNode arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
  10.         int teams[MAX_VERTEX_NUM];
  11.         int vexnum,arcnum;
  12. }AdjMatrix;/*邻接矩阵*/
  13. void Dijkstra(AdjMatrix G, int start,int end);
  14. void DFSTraverse(AdjMatrix G,int start,int end);
  15. void DFS(AdjMatrix G,int start,int end,int path[],int j);
  16. int sum = 0;/*计算可使用队伍总数*/
  17. int length;
  18. int count = 0;/*统计最短路径数目*/
  19. int main()
  20. {
  21.         AdjMatrix G;
  22.         int N,K,C1,C2;
  23.         int c1,c2,L;
  24.         int i,j;
  25.         scanf("%d %d %d %d",&N,&K,&C1,&C2);
  26.         G.vexnum = N;
  27.         G.arcnum = K;
  28.         /*初始化邻接矩阵*/
  29.         for(i = 0;i < G.vexnum;i++)
  30.         {
  31.                 G.vertex[i] = i;
  32.                 scanf("%d",&G.teams[i]);
  33.                 for(j = 0;j < G.vexnum;j++)
  34.                 {
  35.                         G.arc[i][j].length = Inf;
  36.                 }
  37.                 G.arc[i][i].length = 0;
  38.         }
  39.         for(i = 0;i < G.arcnum;i++){
  40.                 scanf("%d %d %d",&c1,&c2,&L);
  41.                 G.arc[c1][c2].length = L;
  42.                 G.arc[c2][c1].length = L;
  43.         }
  44.         Dijkstra(G,C1,C2);       
  45.         DFSTraverse(G,C1,C2);
  46.         printf("%d %d\n",count,sum);
  47.         return 0;
  48. }
  49. void DFSTraverse(AdjMatrix G,int start,int end)
  50. {
  51.         int path[MAX_VERTEX_NUM + 1] ={0};
  52.         path[start] = 1;
  53.         /*path[MAX_VERTEX_NUM] = 0;用于统计路径长度*/
  54.         DFS(G,start,end,path,2);
  55. }
  56. void DFS(AdjMatrix G,int start,int end,int path[],int j)
  57. {
  58.         int i,k,n;
  59.         int flag = 0;
  60.         for(i = 0;i < G.vexnum;i++)
  61.         {
  62.                 if(start == end) break;
  63.                 if(!path[i] && start != i && G.arc[start][i].length < Inf)
  64.                 {
  65.                         if(path[MAX_VERTEX_NUM] + G.arc[start][i].length > length)
  66.                                 continue;
  67.                         path[MAX_VERTEX_NUM] += G.arc[start][i].length;
  68.                         path[i] = j;
  69.                         DFS(G,i,end,path,j + 1);
  70.                         path[MAX_VERTEX_NUM] -= G.arc[start][i].length;
  71.                         path[i] = 0;
  72.                         flag = 1;
  73.                 }
  74.         }
  75.         if(!flag)
  76.         {
  77.                 int temp = 0;
  78.                 for(k = 1;k < j;k++)
  79.                 {
  80.                         for(n = 0;n < G.vexnum;n++)
  81.                                 if(path[n] == k)
  82.                                 {
  83.                                         if(j - 1 == k && n != end)
  84.                                         {
  85.                                                 temp = 0;       
  86.                                                 break;
  87.                                         }
  88.                                         temp += G.teams[n];
  89.                                 }
  90.                 }
  91.                 if(temp != 0) count++;
  92.                 if(temp > sum) sum = temp;
  93.         }
  94. }
  95. /*Dijkstra算法求出最短路径*/
  96. void Dijkstra(AdjMatrix G, int start,int end)
  97. {
  98.         int N = G.vexnum; /*进行N次循环,即进行N次Dijkstra路径优化*/
  99.         int Pre[MAX_VERTEX_NUM];/*用于存放到达该点最近的前一个点*/
  100.         int Min[MAX_VERTEX_NUM];/*表示起点到第i个点的最短距离*/
  101.         int flag[MAX_VERTEX_NUM] = {0};/*置1表示最短距离已经确定,起始为1的点表示起点*/
  102.         int i,min;
  103.         int V = start;
  104.         flag[start] = 1;
  105.         for(i = 0;i < G.vexnum;i++)
  106.                 Min[i] = Inf;
  107.         Min[start] = 0;
  108.         while(N--)
  109.         {
  110.                 for(i = 0;i < G.vexnum;i++)
  111.                 {
  112.                         if(!flag[i] && G.arc[V][i].length + Min[V] < Min[i])
  113.                         {
  114.                                 Min[i] = G.arc[V][i].length + Min[V];
  115.                                 Pre[i] = V;
  116.                         }
  117.                 }
  118.                 for(i = 0,min = Inf;i < G.vexnum;i++)
  119.                 {
  120.                         if(!flag[i] && Min[i] < min)
  121.                         {
  122.                                 min = Min[i];
  123.                                 V = i;
  124.                         }
  125.                 }
  126.                 flag[V] = 1;
  127.         }
  128.         length = Min[end];
  129. }
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
小甲鱼 + 3 + 3 支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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