第二天

A1003 Emergency (25 分)

题目内容

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 Specification:

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, C₁ and C₂ - 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 c₁, c₂ 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 C₁ to C₂.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C₁ and C₂, 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

单词

emergency

英 /ɪ'mɜːdʒ(ə)nsɪ/ 美 /ɪ'mɝdʒənsi/

n. 紧急情况；突发事件；非常时刻
adj. 紧急的；备用的

rescue

英 /'reskjuː/ 美 /'rɛskju/

n. 营救，解救，援救；营救行动

v. 营救，援救；（非正式）防止……丢失

scattered

英 /'skætəd/ 美 /'skætɚd/
adj. 分散的；散乱的

at the mean time

同时

call up

打电话给；召集；使想起；提出

as many hands

尽可能多的人手

guarantee

英 /gær(ə)n'tiː/ 美 /,ɡærən'ti/

n. 保证；担保；保证人；保证书；抵押品
vt. 保证；担保

题目分析

本题是正常的单源最短路问题，使用Dijkstra算法即可解决，只不过在刷新dist（到达每一点的最短路）的时候需要顺便需要刷新num（最短路的条数）与rescue（到达某一点的救援队数量）的数量，关于最短路的条数num，我一开始想的比较简单，只使用了一个整型变量来监测到达终点时的最短路条数，实际上关于最短路的条数和最短路的长度和救援队的数量一样需要不断刷新才能得到最后的结果。

具体代码

#include\
#include\
#include\
#define MAXSIZE 500

int road[MAXSIZE][MAXSIZE];
int team[MAXSIZE];
int rescue[MAXSIZE];
int is_collect[MAXSIZE];
int is_visited[MAXSIZE];
int dist[MAXSIZE];
int num[MAXSIZE];
int N, M, C1, C2;

void Dijkstra();

int main(void)
{
    scanf("%d %d %d %d", &N, &M, &C1, &C2);
    for (int i = 0; i < N; i++)
        scanf("%d", &team[i]);
    for (int i = 0; i < N; i++)
    {
        dist[i] = INT_MAX;
    }
    for (int i = 0; i < M; i++)
    {
        int c1, c2, l;
        scanf("%d %d %d", &c1, &c2, &l);
        road[c1][c2] = l;
        road[c2][c1] = l;
    }
    Dijkstra();
    printf("%d %d", num[C2], rescue[C2]);
    system("pause");
}

int is_trave()
{
    int flag = 1;
    for (int i = 0; i < N; i++)
    {
        if (is_visited[i] != 0 && is_collect[i] == 0)
        {
            flag = 0;
            break;
        }
    }
    return flag;
}

int find_min()
{
    int temp = 0;
    int min = INT_MAX;
    for (int i = 0; i < N; i++)
    {
        if (is_visited[i] == 1 && is_collect[i] == 0)
        {
            if (dist[i] < min)
            {
                min = dist[i];
                temp = i;
            }
        }
    }
    return temp;
}

void Dijkstra()
{
    is_collect[C1] = 1;
    rescue[C1] = team[C1];
    num[C1] = 1;
    for (int i = 0; i < N; i++)
    {
        if (road[C1][i] != 0)
        {
            is_visited[i] = 1;
            dist[i] = road[C1][i];
            num[i] = num[C1];
            rescue[i] = rescue[C1] + team[i];
        }
    }
    while (!is_trave())
    {
        int m = find_min();
        is_collect[m] = 1;
        for (int i = 0; i < N; i++)
        {
            if (road[m][i] != 0&&is_collect[i]==0)
            {
                if (dist[m] + road[m][i] < dist[i])
                {
                    num[i] = num[m];
                    dist[i] = dist[m] + road[m][i];
                    rescue[i] = rescue[m] + team[i];
                }
                else if (dist[m] + road[m][i] == dist[i])
                {
                    num[i] = num[i] + num[m];
                    if (rescue[m] + team[i] > rescue[i])
                        rescue[i] = rescue[m] + team[i];
                }
                is_visited[i] = 1;
            }
        }
    }
}

参考博客

1003. Emergency (25)-PAT甲级真题（Dijkstra算法）