PTA ladder game exercise set l2-001 inter city emergency rescue

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