L2-001 emergency rescue (25 points) (Dijkstra comprehensive application)

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

  Ideas ： A very simple question , A comprehensive investigation dijkstra. Need to find the shortest path length , Number of shortest paths , What points does the path pass through , And the addition of some added values passing through the point .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,c1,c2;
int f[580];  // It is used to record which points the shortest path from the source point to a point passes through 
int num[591];
int sum[591];  // Record the sum of the added value of the passing point in the shortest path from the source point to each point 
int e[591][592];
int book[590];
int dis[591];
int cnt[505];
void hs(int c2,int c1){
    if(c2==c1){
        cout<<c1;
        return ;
    }else{
        hs(f[c2],c1);
        cout<<" "<<c2;
        return ;
    }
}
void dijkstra(){
    cnt[c1]=1;  // Use source point 
    memset(dis,0x3f3f3f3f,sizeof(dis));
    sum[c1]=num[c1];  // Use source point 
    dis[c1]=0;
    int i,j;
    for(i=0;i<n;i++){     //n individual , From the source 
        int now=-1;
        int tmp=0x3f3f3f3f;
        for(j=0;j<n;j++){
            if(book[j]==0&&(now==-1||dis[j]<tmp)){  //now==-1 Then we can deal with disconnected graphs 
                now=j;
                tmp=dis[j];
            }
        }
        book[now]=1;
        for(j=0;j<n;j++){
            if(dis[j]>dis[now]+e[now][j]){
                dis[j]=dis[now]+e[now][j];
                f[j]=now;
                sum[j]=sum[now]+num[j];
                cnt[j]=cnt[now];
            }else if(dis[j]==dis[now]+e[now][j]){
                if(sum[j]<sum[now]+num[j]){
                    f[j]=now;
                    sum[j]=sum[now]+num[j];
                }
                cnt[j]=cnt[j]+cnt[now];  // If the path length is the same, the number of shortest paths is added 
            }
        }
    }
    return ;
}
int main (){
    cin>>n>>m>>c1>>c2;
    int i,j;
    for(i=0;i<n;i++){
        cin>>num[i];
    }
    memset(e,0x3f3f3f3f,sizeof(e));// Be careful , Here is the e[i][i] That is, the distance from oneself to oneself is defined as inf
    for(i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u][v]=min(e[u][v],w);
        e[v][u]=min(e[v][u],w);
    }
    dijkstra();
    cout<<cnt[c2]<<" "<<sum[c2]<<endl;
    hs(c2,c1);
    return 0;
}