当前位置:网站首页>PTA ladder game exercise set l2-001 inter city emergency rescue
PTA ladder game exercise set l2-001 inter city emergency rescue
2022-07-02 15:37:00 【qascetic】
Intercity emergency
As the leader of a city's emergency rescue team , You have a special national map . On the map, there are many scattered cities and some fast roads connecting the cities . The number of rescue teams in each city and the length of each expressway connecting the two cities are marked on the map . When other cities have an emergency call for you , Your task is to lead your rescue team to catch up as soon as possible , meanwhile , Gather as many rescue teams as you can along the way .
Input format :
The first line of input is given 4 A positive integer N、M、S、D, among N(2≤N≤500) It's the number of cities , By the way, suppose the city number is 0 ~ (N−1);M It's the number of expressways ;S It's the city number of the place of departure ;D Is the city number of the destination .
The second line gives N A positive integer , Among them the first i The number is the i Number of rescue teams in cities , Numbers are separated by spaces . And then M In line , Each line gives information about an expressway , Namely : City 1、 City 2、 The length of the Expressway , Separate... With spaces in the middle , All numbers are integers and no more than 500. The input ensures that the rescue is feasible and the optimal solution is unique .
Output format :
The first line outputs the shortest path number and the maximum number of rescue teams that can be called . The second line is output from S To D The number of the city in the path . Numbers are separated by spaces , There must be no extra spaces at the end of the output .
sample input :
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
sample output :
2 60
0 1 3
General train of thought :Dijsktra The algorithm finds the shortest path , Slightly modify the algorithm to choose to carry as many rescue team members as possible when finding the shortest path . About Dijsktra Click on the portal below to learn more about the algorithm . I won't elaborate on this blog .
Portal :Dijsktra Algorithm analysis
AC Code (C++)
#include <iostream>
#include<algorithm>
#define MAXNUM 501 // The maximum number of questions given does not exceed 500
#define INF 100000000 // Assume infinite numbers
using namespace std;
int peoples[MAXNUM]; // Save the number of rescue workers in each city , The index of the array is the city number
int peopleSum[MAXNUM] = {
0 }; // Save the total number of rescuers
int graph[MAXNUM][MAXNUM] = {
0 }; // Save adjacency matrix
int waySum[MAXNUM] = {
0 }; // Save the path
bool visit[MAXNUM] = {
false }; // Mark vertex accessed
int prevNode[MAXNUM]; // Record the precursor vertex of the current vertex
int dist[MAXNUM]; // Save shortest path
int inAllNum; // Number of all cities , That is, the number of cities entered
void print(int end, int start) // Recursively print from back to front , Always look for the precursor node from the end
{
if (start == end)
{
cout << end;
return;
}
print(prevNode[end], start);
cout << " " << end;
}
void Dijkstra(int start)
{
fill(dist, dist + inAllNum, INF); // Suppose at first all places are infinitely far away from each other
peopleSum[start] = peoples[start]; // The number of rescue team members at the starting point is directly added to the total
waySum[start] = 1; // There is at least one way from the starting point
dist[start] = 0; // We can think that the distance from the starting point to the starting point is 0
int minNum = INF; // Record the minimum distance between the current two cities , Initialize to infinity
int nodeNum = -1; // Record the city vertex number , Initialize to -1
// Cycle through all cities
for (int i = 0; i < inAllNum; i++)
{
// The two variables that record the minimum distance between cities and the city vertex need to be initialized once every cycle
minNum = INF; // Store the shortest distance from the starting point to other inaccessible nodes
nodeNum = -1; // Store the number of the shortest distance node
// Traverse n vertices , Find the node number with the shortest distance from the starting vertex in the currently unreached vertex
for (int j = 0; j < inAllNum; j++)
// visit[j] yes false Then it is not visited , Expression is true
// The shortest distance is less than the current minNum Stored data , Expression is true
// If the above conditions are met, you can enter the judgment
if (!visit[j] && minNum > dist[j])
{
minNum = dist[j];
nodeNum = j;
}
if (-1 == nodeNum) // If the condition is not found, jump out of the loop
break;
visit[nodeNum] = true; // Mark the currently selected vertex as visited
// With nodeNum Traverse other vertices and calculate the distance for the intermediate node
for (int j = 0; j < inAllNum; j++)
{
// If the currently traversed node j Never used as an intermediate node
// And from the starting node to j Distance of dist[j] Greater than from the starting node to nodeNum And from the nodeNum To j The sum of the distances
if (!visit[j] && dist[j] > dist[nodeNum] + graph[nodeNum][j])
{
// Update start node to j Distance of dist[j], Update to start to nodeNum And nodeNum To j The sum of the distances
dist[j] = dist[nodeNum] + graph[nodeNum][j];
// Record the number of rescue teams
peopleSum[j] = peopleSum[nodeNum] + peoples[j];
// Record the precursor node of the current vertex
prevNode[j] = nodeNum;
// Record the number of paths
waySum[j] = waySum[nodeNum];
}
// If the currently traversed node j Never used as an intermediate node
// And from the starting node to j Distance of dist[j] Equal to from the starting node to nodeNum And from the nodeNum To j The sum of the distances
else if (!visit[j] && dist[j] == dist[nodeNum] + graph[nodeNum][j])
{
// This sentence makes little sense because a = 1, a == b then a = b,a Or is it equal to 1 Assignment is of little significance
// dist[j] = dist[nodeNum] + graph[nodeNum][j];
// If you pass by nodeNum If there are more vertex rescue team members, update the number of rescue team members, and then modify the precursor vertex
if (peopleSum[j] < peopleSum[nodeNum] + peoples[j])
{
// Update the number of rescue team , Try to have more rescue team members
peopleSum[j] = peopleSum[nodeNum] + peoples[j];
// If you change the driving route, you have to update the corresponding precursor nodes
prevNode[j] = nodeNum;
}
// Because there are two roads with the same distance, you can choose all the roads in these two days, plus nodeNum The number of paths of vertices
// Not directly waySum[j]++, Because after nodeNum There is not only one path in the vertex scheme
waySum[j] += waySum[nodeNum];
}
}
}
}
int main()
{
//N(2≤N≤500) It's the number of cities , By the way, suppose the city number is 0 ~ (N−1);
//M It's the number of expressways ;
//S It's the city number of the place of departure ;
//D Is the city number of the destination .
int N, M, S, D;
cin >> N >> M >> S >> D;
//inAllNum Also count the number of cities , Global variables are convenient for other functions to access
inAllNum = N;
// Enter the number of rescue teams in each city in turn
for (int i = 0; i < N; i++)
cin >> peoples[i];
// Initialize adjacency matrix
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (i != j)
graph[i][j] = INF;
// Assign a value to the adjacency matrix
int tempa, tempb, tempc;
for (int i = 0; i < M; i++)
{
cin >> tempa >> tempb >> tempc;
graph[tempa][tempb] = tempc;
graph[tempb][tempa] = tempc;
}
Dijkstra(S);
cout << waySum[D] << " " << peopleSum[D] << endl;
print(D, S);
return 0;
}
Here are some test samples , Friends who fail the test can try .
Examples (1)
6 6 0 3
30 10 20 50 20 20
0 1 1
2 3 3
0 4 1
1 2 2
5 3 3
4 5 2
Examples (2)
6 7 0 3
30 100 20 50 20 20
1 3 5
2 3 3
1 2 2
5 3 3
0 4 1
4 5 2
0 1 1
Examples (3)
5 5 0 3
30 100 20 50 120
0 4 1
0 1 1
1 2 1
4 3 5
2 3 3
Examples (4)
7 8 0 6
10 20 30 50 30 30 20
0 1 1
0 2 1
1 3 2
5 6 4
3 4 3
3 5 3
4 6 4
2 3 2
边栏推荐
- 【网络安全】网络资产收集
- YOLOV5 代码复现以及搭载服务器运行
- JVM architecture, classloader, parental delegation mechanism
- 5. Practice: jctree implements the annotation processor at compile time
- 【LeetCode】189-轮转数组
- 【LeetCode】1140-石子游戏II
- 飞凌嵌入式RZ/G2L处理器核心板及开发板上手评测
- 17_ Redis_ Redis publish subscription
- [leetcode] 877 stone game
- How does the computer set up speakers to play microphone sound
猜你喜欢
Yolo format data set processing (XML to txt)
Beijing rental data analysis
Solve the problem of frequent interruption of mobaxterm remote connection
党史纪实主题公益数字文创产品正式上线
基于RZ/G2L | OK-G2LD-C开发板存储读写速度与网络实测
Data analysis thinking analysis methods and business knowledge - business indicators
Yolov5 code reproduction and server operation
MySQL -- Index Optimization -- order by
Case introduction and problem analysis of microservice
SQL stored procedure
随机推荐
FPGA - 7系列 FPGA内部结构之Clocking -03- 时钟管理模块(CMT)
Loss function and positive and negative sample allocation: Yolo series
Leetcode skimming -- verifying the preorder serialization of binary tree # 331 # medium
高考录取分数线爬虫
08_ strand
03_ Linear table_ Linked list
04_ Stack
损失函数与正负样本分配:YOLO系列
Yolo format data set processing (XML to txt)
Data analysis thinking analysis methods and business knowledge - business indicators
Let your HMI have more advantages. Fet-g2ld-c core board is a good choice
夏季高考文化成绩一分一段表
16_Redis_Redis持久化
【LeetCode】695-岛屿的最大面积
做好抗“疫”之路的把关人——基于RK3568的红外热成像体温检测系统
(Video + graphic) machine learning introduction series - Chapter 5 machine learning practice
党史纪实主题公益数字文创产品正式上线
SQL stored procedure
飞凌嵌入式RZ/G2L处理器核心板及开发板上手评测
士官类学校名录