PAT Advanced 1003. Emergency
1. Problem Description:
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.
2. 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_1\) and \(C_2\) - 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_1\), \(c_2\) 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_1\) to \(C_2\).
3. Output Specification:
For each test case, print in one line two numbers: the number of different shortest paths between \(C_1\) and \(C_2\), 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.
4. 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
5. Sample Output:
2 4
6. Performance Limit:
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
思路：
题目涉及图这种数据结构，每个城市作为一个顶点，城市间道路作为边，道路长度作为边的权重，题目即要求找出两顶点间最短路径的条数（可能不止一条），以及这些最短路径中救援队数目总和的最大值。这里采用邻接矩阵对图进行表示，定义子函数traverseMap()对图进行递归遍历，找出顶点 \(C_1\) 和 \(C_2\) 间的所有可行路径，定义map<int, int> 类型变量roadCount存储所有可行路径的长度，定义multimap<int, int> 类型变量teamCount存储所有可行路径的救援队总和，最后按要求进行输出即可。定义递归子函数需要注意维护访问标志visitFlag，保证所有顶点只被访问1次，不然可能出现递归无法结束的情况。。。这里第一次提交时testpoint1，2，3，4，5报wrong answer，检查后发现输出部分的逻辑处理存在问题，修改后testpoint2，3，4，5通过，testpoint1仍然报wrong answer，考虑边界条件后发现忽略了顶点 \(C_1,C_2\) 是同一点的情况，增加判断后通过testpoint1。
参考大佬题解：1003. Emergency (25)-PAT甲级真题（Dijkstra算法）_柳婼的博客-CSDN博客 ，采用了Dijkstra算法，只能瑟瑟发抖（之前看过数据结构和算法但是全忘了）。
My Code & Result:
#include <iostream>
#include <vector>
#include <map>
using namespace std;
void traverseMap(vector<vector<int>> &road, int n, int c1, int c2, int lenSum, map<int, int> &roadCount, vector<int> visitFlag, const int *teamNum, int teamSum, multimap<int, int> &teamCount);
// first submit testpoint 1, 2, 3, 4, 5 wrong answer
int main(void)
{
int n=0, m=0, c1=0, c2=0;
int i=0; // iterator
int tempI=0, tempJ=0, tempLen=0;
map<int, int> roadCount; // key: roadLen, value: correspond road count
multimap<int, int> teamCount; // key: roadLen, value: gatherd team count
int pathNum=0, maxTeam=0;
int minPath=0;
cin >> n >> m >> c1 >> c2;
int teamNum[n] = {0};
for(i=0; i<n; ++i)
{
cin >> teamNum[i];
//cout << teamNum[i] << endl;
}
if(c1 == c2) // this fixed testpoint 1
{
cout << "1 " << teamNum[c1] << endl;
return 0;
}
//int road[n][n] = {0}; // this way some element will not initialize to 0. It's strange
vector<vector<int>> road(n, vector<int>(n, 0));
for(i=0; i<m; ++i) // input the road length
{
cin >> tempI >> tempJ >> tempLen;
road[tempI][tempJ] = tempLen;
road[tempJ][tempI] = tempLen;
}
vector<int> visitFlag(n, 0);
visitFlag[c1] = 1;
traverseMap(road, n, c1, c2, 0, roadCount, visitFlag, teamNum, teamNum[c1], teamCount);
pathNum = roadCount.begin()->second;
minPath = roadCount.begin()->first; // this fixed testpoint 2, 3, 4, 5
maxTeam = -1;
for(const auto &w: teamCount)
{
if(w.first == minPath && w.second > maxTeam) // if(w.first == pathNum && w.second > maxTeam)
{
maxTeam = w.second;
}
}
//cout << roadCount.begin()->second << endl;
cout << pathNum << ' ' << maxTeam << endl;
//cout <<
// for(const auto &w: roadCount) // range for
// {
// cout << w.first << ": " << w.second << endl;
// }
// for(const auto &w: teamCount)
// {
// cout << w.first << ": " << w.second << endl;
// }
// for(i=0; i<n; ++i) // output road info
// {
// for(j=0; j<n; ++j)
// {
// //road[i][j] = 0;
// cout << road[i][j] << ' ';
// }
// cout << endl;
// }
return 0;
}
void traverseMap(vector<vector<int>> &road, int n, int c1, int c2, int lenSum, map<int, int> &roadCount, vector<int> visitFlag, const int *teamNum, int teamSum, multimap<int, int> &teamCount) // learn use vector as parameter
{
int i=0; // iterator
for(i=0; i<n; ++i)
{
if(road[c1][i] && !visitFlag[i]) // c1 -> i have road && i doesn't visited
{
if(i==c2) // have road, save the length directly
{
//lenSum += road[c1][c2];
++roadCount[lenSum+road[c1][c2]];
teamCount.insert({lenSum+road[c1][c2], teamSum+teamNum[c2]});
}
else // doesn't have direct road
{
vector<int> tempVist = visitFlag;
tempVist[i] = 1;
traverseMap(road, n, i, c2, lenSum+road[c1][i], roadCount, tempVist, teamNum, teamSum+teamNum[i], teamCount);
}
}
}
return;
// if(road[c1][c2]) // have road, save the length directly
// {
// lenSum += road[c1][c2];
// ++roadCount[lenSum];
// return;
// }
// else // doesn't have direct road
// {
// for(i=0; i<n; ++i)
// {
// if(road[c1][i]) // c1 -> i have road
// {
// traverseMap(road, n, i, c2, lenSum+road[c1][i], roadCount);
// }
// }
// }
// return;
// int i=0, j=0;
// for(i=0; i<n; ++i) // output road info
// {
// for(j=0; j<n; ++j)
// {
// //road[i][j] = 0;
// cout << road[i][j] << ' ';
// }
// cout << endl;
// }
}
Compiler
C++ (g++)
Memory
3608 / 65536 KB
Time
336 / 400 ms