1003 Emergency (25分)
1003 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,
C1and 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 Specification:
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
采用迪杰斯特拉算法解决
在迪杰斯特拉的基础上统计出最短路径的条数和最短路径的长度即可
#include<iostream>
using namespace std;
const int MAX = 505;
const int MAX_int = 0x7fffffff;
int call[MAX], map[MAX][MAX];//call为每个城市救援队的数量，map为地图
struct City//实现类内初始化
{
int dist = MAX_int;
int num = 0;//num为路径数
int call_num = 0;//为救援队总数
bool visit = 0;
};
City city[MAX];
void Dijkstra(int star, int end, int N)
{
//首先处理star城市
city[star].dist = 0;
city[star].call_num = call[star];
city[star].num = 1;//从star到star共一种方式
for (int i = 0; i < N; ++i)
{
int min = MAX_int, pos = -1;
//查找没有访问过的城市中最近的那个
for (int j = 0; j < N;++j)
{
if (city[j].visit == 0 && city[j].dist < min)
{
pos = j;
min = city[j].dist;
}
}
if (pos == -1)break;//如果为-1说明完成
city[pos].visit = 1;
for (int i = 0; i < N; ++i)
{
//根据pos更新数据，若通过pos到达i点距离更近则从pos到达i点
//若从pos到i与原路径相同，则选择救援队最多的路径
//call_num加上即为选择上
if (map[pos][i] != MAX_int &&city[i].visit == 0 && city[i].dist > min + map[pos][i])
{
city[i].call_num= city[pos].call_num+call[i];
city[i].num = city[pos].num;
city[i].dist = city[pos].dist + map[i][pos];
}
else if (map[pos][i] != MAX_int && city[i].visit == 0 && city[i].dist ==(city[pos].dist + map[pos][i]))
{
city[i].num += city[pos].num;
if (city[i].call_num < city[pos].call_num + call[i])
city[i].call_num = city[pos].call_num + call[i];
}
}
}
cout << city[end].num << " " << city[end].call_num;
}
int main()
{
int N, M, C1, C2;
cin >> N >> M >> C1 >> C2;
for (int i = 0; i < N; ++i)
{
cin >> call[i];
}
//初始化地图上每个点的距离为无限大
for (int i=0,j=0;i<N;++i)
{
for (j = 0; j < N; ++j)
{
map[i][j] = MAX_int;
}
}
int a, b,len;
//根据输入数据修改地图上的距离
for (int i = 0; i < M; ++i)
{
cin >> a >> b >> len;
map[a][b] =len;
map[b][a] = len;
}
Dijkstra(C1, C2, N);
}```
