Hugh

门泊东吴万里船

0%

PAT-1003_Emergency

Posted on Edited on In

1003 Emergency

题意

给定每个城市间的距离和每个城市可获得的助手数量，寻找最短的路径以及能获得最多的助手数

思路

此题就是求解最短路径，只是在求解的过程中需要记录有几个最短路径，以及在所有最短路径中权重最大的值。
求解最短路径使用的是Dijkstra算法，在这道题中，需要做一下变化记录下最短路径数，和最大权重

源码

line_number: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <stdio.h>
#include <map>
using namespace std;
int main()
{
    int N, M, C1, C2;
    cin>>N >>M >>C1 >> C2;
    int hands[N]; // 城市助手数量
    int roads[N][N]; // 两座城市的路费
    int visited[N]; //该城市是否已经访问
    int shortRoads[N]; //最短路径长度
    int shortRoadsNum[N]; //最短路径数量
    int maxHands[N]; //到该城市最多的人数
    for(int i = 0; i < N; i++)
    {
        cin>>hands[i];
        visited[i] = 0; //初始化所有城市未访问
        shortRoads[i] = -1; //初始化所有城市最短路径都不存在
        shortRoadsNum[i] = 0; // 初始化所有的城市最短路径数量为0
        maxHands[i] = 0;
        for(int j = 0;j < N; j++)
        {
            roads[i][j] = -1; //初始化两座城市不可达
        }
    }
    for(int i = 0; i < M; i++)
    {
        int c1, c2, L;
        cin >> c1 >> c2 >> L;
        roads[c1][c2] = L;
        roads[c2][c1] = L;
    }
    shortRoads[C1] = 0;
    shortRoadsNum[C1] = 1;
    maxHands[C1] = hands[C1];
    for(int i = 0; i < N; i++)
    {
        int nowMinRoadCity = -1;
        int nowMinRoad = -1;
        for(int j = 0; j < N; j++) //寻找当前距离最小的节点
        {
            if(visited[j] == 0 && shortRoads[j] != -1)//目前不可达的城市不考虑
            {
                if(nowMinRoad == -1 || nowMinRoad > shortRoads[j])
                {
                    nowMinRoad = shortRoads[j];
                    nowMinRoadCity = j;
                }
            }
        }
        if(nowMinRoad == -1) //如果没找到未访问过的城市的最小路径则结束
        {
            break;
        }
    //        cout<<"nowMinRoadCity:" << nowMinRoadCity <<endl;
        visited[nowMinRoadCity] = 1;

        for(int j = 0; j < N; j++) //在最小节点的基础上更新路径
        {
            if(visited[j] == 0) //
            {
                if(shortRoads[j] == -1) //当前城市处于不可达的状态
                {
                   if(roads[nowMinRoadCity][j] != -1)
                   {
                       shortRoads[j] = shortRoads[nowMinRoadCity] + roads[nowMinRoadCity][j];
                       shortRoadsNum[j] = shortRoadsNum[nowMinRoadCity] ;
                       if(maxHands[j] < maxHands[nowMinRoadCity] + hands[j])
                       {
                           maxHands[j] = maxHands[nowMinRoadCity] + hands[j];
                       }
                   }
                }
                else
                {
                    if(roads[nowMinRoadCity][j] != -1)
                    {
                        if(shortRoads[j] > shortRoads[nowMinRoadCity] + roads[nowMinRoadCity][j])
                        {
                            shortRoads[j] = shortRoads[nowMinRoadCity] + roads[nowMinRoadCity][j];
                            shortRoadsNum[j] = shortRoadsNum[nowMinRoadCity];
                            if(maxHands[j] < maxHands[nowMinRoadCity] + hands[j])
                            {
                                maxHands[j] = maxHands[nowMinRoadCity] + hands[j];
                            }
                        }
                        else if(shortRoads[j] == shortRoads[nowMinRoadCity] + roads[nowMinRoadCity][j])
                        {
                            shortRoadsNum[j] += shortRoadsNum[nowMinRoadCity];
                            if(maxHands[j] < maxHands[nowMinRoadCity] + hands[j])
                            {
                                maxHands[j] = maxHands[nowMinRoadCity] + hands[j];
                            }
                        }
                    }

                }
    //                cout<< "shortRoads " <<j << " " <<shortRoads[j]<<endl;
            }
        }
    }
    cout<< shortRoadsNum[C2]<< " " << maxHands[C2]<<endl;
    return 0;
}