山河永寂,人间长情

0%

PAT (Advanced Level)-1003. Emergency (25)

PAT (Advanced Level)-1003. Emergency

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.

每次输入即一个测试案例。对于每个测试案例,第一行包含4个正整数:
N(<= 500)是城市的数量(城市从0到N-1编号), M 表示道路数量, C1和C2 分别是你目前所在的城市和你将要去救援的城市编号。
下一行包含N个整数,其中第i个整数表示第i个城市中的救援队伍的数量。
随后的M行,每行用c1,c2和L描述一条道路,它们分别是道路连接的两个城市城市和该道路的长度。
保证从C1到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.

对于每个测试案例,在一行中打印两个数字:C1和C2之间不同的最短路径的数量,以及在前往救援过程中可能收集到的最大救援队伍。
一行中的所有数字必须以正好一个空格分隔,并且在行末尾不允许有额外的空格。

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


解读

这道题目很显然的在考察“最短路径”算法,但是需要注意的是,题目中的最短路径并不只有一条,所以需要对原有算法进行稍微修改,以存储多条最短路径及路径信息。

完整代码

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
#include<iostream>       
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 500;

//创建题目条件中所有输入用的变量
int N, M, C1, C2, startCity, endCity, length;
//定义存储救援队数目、距离、地图(邻接矩阵)、条件判断标注数组、输出结果数组
int v[MAX], dis[MAX], map[MAX][MAX], vis[MAX], ans[MAX];
//定义存储路径数组
long long cnt[MAX];

int main()
{
//输入题目中的N、M、C1、C2
cin >> N >> M >> C1 >> C2;

//存储救援队数量
for (int i = 0; i < N; i++) cin >> v[i];

//初始化地图(邻接矩阵)为-1
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
map[i][j] = -1;

//初始化路径距离数组为-1
for (int i = 0; i < MAX; i++)
dis[i] = -1;

//输入地图(邻接矩阵)信息
while (M--)
{
cin >> startCity >> endCity >> length;
map[startCity][endCity] = map[endCity][startCity] = length;
}


ans[C1] = v[C1]; dis[C1] = 0; cnt[C1] = 1;

//Dijkstra算法
while (true)
{
int now = -1;
for (int i = 0; i < N; i++)
{
if (!vis[i] && dis[i] != -1)
{
if (now == -1)
now = i;
else
now = dis[now] < dis[i] ? now : i;
}
}

if (now == -1) break;
vis[now] = 1;

for (int i = 0; i < N; i++)
{
if (map[now][i] != -1)
{
if (dis[i] == -1 || dis[i] > dis[now] + map[now][i])
{
dis[i] = dis[now] + map[now][i];
cnt[i] = cnt[now];
ans[i] = ans[now] + v[i];
}
else if (dis[i] == dis[now] + map[now][i])
{
cnt[i] += cnt[now];
ans[i] = max(ans[i], ans[now] + v[i]);
}
}
}
}

cout<<cnt[C2]<<" "<<ans[C2];
return 0;
}