admin管理员组文章数量:1577538
1003 Emergency
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.
基本用例:
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
输出:
2 4
其他2:
测试点2、4
5 6 0 4
1 2 1 5 3
0 1 1
0 2 2
0 3 2
1 2 1
2 4 1
3 4 1
输出
3 9
其他3:
测试点2、4
5 6 0 4
1 1 1 1 1
0 1 1
0 2 2
0 3 2
1 2 1
2 4 1
3 4 1
输出:
3 4
其他4:
输入:
5 4 0 4
1 1 1 1 1
0 2 2
0 3 1
2 3 1
2 4 1
输出:
2 4
实现代码:
100%pass
#include <iostream>
#include<vector>
using namespace std;
struct Path {
int end;
int length;
Path(int end, int length) :end(end), length(length) {}
};
void getPathsAndMinLength(int start, int end, int citys, vector<Path>* graph, vector<int>* teams) {
bool* visited = new bool[citys];
//设置为未访问
for (int i = 0; i < citys; i++)
{
visited[i] = false;
}
// 初始化当前路径
int* pathLength = new int[citys];
vector<int>* pre = new vector<int>[citys];
int* weight = new int[citys];
int* num = new int[citys];
for (int i = 0; i < citys; i++)
{
if (i == start)
{
pathLength[i] = 0;
num[i] = 1;
pre[i].push_back(start);
weight[i] = (*teams)[i];
}
else {
pathLength[i] = 0x3FFFFFFF;
num[i] = 0;
weight[i] = 0;
}
}
for (int i = 0; i < graph[start].size(); i++)
{
pathLength[graph[start][i].end] = graph[start][i].length;
pre[graph[start][i].end].push_back(start);
weight[graph[start][i].end] = weight[start] + (*teams)[graph[start][i].end];
num[graph[start][i].end] = num[start];
}
bool hasUnvisted = true;
visited[start] = true;
while (hasUnvisted)
{
hasUnvisted = false;
if (visited[end] == true)
{
break;
}
// 选取当前最短的路径访问
int minPath = 0X3FFFFFFF, nextNode = 0;
for (int i = 0; i < citys; i++)
{
//未访问过而且当前到原点start的路径最短
if (visited[i] == false && minPath > pathLength[i]) {
minPath = pathLength[i];
nextNode = i;
hasUnvisted = true;
}
}
if (hasUnvisted)
{
visited[nextNode] = true;
// 如果还有没有访问,但是可以访问的点,则以这个点为中间点继续访问
vector<Path> path = graph[nextNode];
for (int i = 0; i < path.size(); i++)
{
// 如果没有访问过,
if (visited[path[i].end] == false && path[i].length < 0x3FFFFFFF) {
if (pathLength[nextNode] + path[i].length < pathLength[path[i].end])
{
pathLength[path[i].end] = pathLength[nextNode] + path[i].length;
pre[path[i].end].clear();
pre[path[i].end].push_back(nextNode);
num[path[i].end] = num[nextNode];
weight[path[i].end] = weight[nextNode] + (*teams)[path[i].end];
}
else if (pathLength[nextNode] + path[i].length == pathLength[path[i].end])
{
// 遇到了相同长度的路径,经过更多的中间节点的救援队更好
if (weight[nextNode] + (*teams)[path[i].end] > weight[path[i].end])
{
weight[path[i].end] = weight[nextNode] + (*teams)[path[i].end];
}
num[path[i].end] += num[nextNode];
pre[path[i].end].push_back(nextNode);
}
}
}
}
}
cout << num[end] << " " << weight[end] << endl;
}
int main()
{
int citys, roads, now, toCity;
cin >> citys >> roads >> now >> toCity;
vector<int> teams;
int team;
for (int i = 0; i < citys; i++)
{
cin >> team;
teams.push_back(team);
}
vector<Path>* graph = new vector<Path>[citys];
int start, end, length;
for (int i = 0; i < roads; i++)
{
cin >> start >> end >> length;
graph[start].push_back(Path(end, length));
graph[end].push_back(Path(start, length));
}
getPathsAndMinLength(now, toCity, citys, graph, &teams);
}
版权声明:本文标题:【pat】1003 Emergency 关于测试用例2、3、4的一点想法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1727821431a1131758.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论