This problem involves finding optimal emergency rescue routes through a network of cities. Given a map with cities, roads, and rescue teams, the objective is to reach a destination city via shortest path while maximizing the number of rescue teams gathered along the way.

Input Specifications:

• First line: Four integers N, M, S, D
  • N: Number of cities (2 ≤ N ≤ 500), cities numbered 0 to N-1
  • M: Number of roads
  • S: Starting city
  • D: Destination city
• Second line: N integers representing rescue team counts in each city
• Next M lines: Road information (city1, city2, road_length)

Output Requirements:

• First line: Number of shortest paths and maximum rescue teams
• Second line: Path from S to D (city numbers separated by spaces)

Example:

Input:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

Output:
2 60
0 1 3

Implementation:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAX_CITIES = 505;
const int INF = INT_MAX;

int roadNetwork[MAX_CITIES][MAX_CITIES];
int dist[MAX_CITIES];
int rescueTeams[MAX_CITIES];
int maxRescue[MAX_CITIES];
int pathCount[MAX_CITIES];
int previous[MAX_CITIES];
bool visited[MAX_CITIES];

int cityCount, roadCount, startCity, destCity;

void findOptimalPath() {
    pathCount[startCity] = 1;
    visited[startCity] = true;
    maxRescue[startCity] = rescueTeams[startCity];
    
    while (true) {
        int currentCity = cityCount;
        for (int i = 0; i < cityCount; i++) {
            if (!visited[i] && dist[i] < dist[currentCity]) {
                currentCity = i;
            }
        }
        
        if (currentCity == cityCount) break;
        visited[currentCity] = true;
        
        for (int neighbor = 0; neighbor < cityCount; neighbor++) {
            if (!visited[neighbor]) {
                int newDist = dist[currentCity] + roadNetwork[currentCity][neighbor];
                
                if (dist[neighbor] > newDist) {
                    dist[neighbor] = newDist;
                    pathCount[neighbor] = pathCount[currentCity];
                    maxRescue[neighbor] = maxRescue[currentCity] + rescueTeams[neighbor];
                    previous[neighbor] = currentCity;
                } else if (dist[neighbor] == newDist) {
                    pathCount[neighbor] += pathCount[currentCity];
                    
                    if (maxRescue[neighbor] < maxRescue[currentCity] + rescueTeams[neighbor]) {
                        maxRescue[neighbor] = maxRescue[currentCity] + rescueTeams[neighbor];
                        previous[neighbor] = currentCity;
                    }
                }
            }
        }
    }
}

int main() {
    cin >> cityCount >> roadCount >> startCity >> destCity;
    
    for (int i = 0; i < cityCount; i++) {
        for (int j = 0; j < cityCount; j++) {
            roadNetwork[i][j] = INF;
        }
    }
    
    for (int i = 0; i < cityCount; i++) {
        visited[i] = false;
        cin >> rescueTeams[i];
    }
    
    for (int i = 0; i < roadCount; i++) {
        int cityA, cityB, length;
        cin >> cityA >> cityB >> length;
        roadNetwork[cityA][cityB] = roadNetwork[cityB][cityA] = length;
    }
    
    for (int i = 0; i < cityCount; i++) {
        dist[i] = roadNetwork[startCity][i];
        if (dist[i] != INF) previous[i] = startCity;
        if (startCity != i && roadNetwork[startCity][i] != INF) {
            maxRescue[i] = rescueTeams[i] + rescueTeams[startCity];
            pathCount[i] = 1;
        }
    }
    
    dist[cityCount] = INF;
    findOptimalPath();
    
    cout << pathCount[destCity] << " " << maxRescue[destCity] << endl;
    
    vector<int> route;
    int current = destCity;
    while (true) {
        route.push_back(previous[current]);
        current = previous[current];
        if (current == startCity) break;
    }
    
    for (int i = route.size() - 1; i >= 0; i--) {
        cout << route[i] << " ";
    }
    cout << destCity;
    
    return 0;
}

The algorithm uses Dijkstra's method with modifications to track multiple optimal paths and maximize rescue team collection. Key components include distance tracking, path counting, rescue team accumulation, and path reconstruction.