作為一個(gè)城市的應(yīng)急救援隊(duì)伍的負(fù)責(zé)人叠纹，你有一張?zhí)厥獾娜珖?guó)地圖氓润。在地圖上顯示有多個(gè)分散的城市和一些連接城市的快速道路。每個(gè)城市的救援隊(duì)數(shù)量和每一條連接兩個(gè)城市的快速道路長(zhǎng)度都標(biāo)在地圖上。當(dāng)其他城市有緊急求助電話給你的時(shí)候斤富，你的任務(wù)是帶領(lǐng)你的救援隊(duì)盡快趕往事發(fā)地，同時(shí)锻狗，一路上召集盡可能多的救援隊(duì)满力。

輸入格式：
輸入第一行給出4個(gè)正整數(shù)N、M轻纪、S油额、D，其中N（2<=N<=500）是城市的個(gè)數(shù)刻帚，順便假設(shè)城市的編號(hào)為0~(N-1)潦嘶；M是快速道路的條數(shù)；S是出發(fā)地的城市編號(hào)崇众；D是目的地的城市編號(hào)掂僵。第二行給出N個(gè)正整數(shù)，其中第i個(gè)數(shù)是第i個(gè)城市的救援隊(duì)的數(shù)目顷歌，數(shù)字間以空格分隔锰蓬。隨后的M行中，每行給出一條快速道路的信息眯漩，分別是：城市1芹扭、城市2、快速道路的長(zhǎng)度赦抖，中間用空格分開舱卡，數(shù)字均為整數(shù)且不超過500。輸入保證救援可行且最優(yōu)解唯一队萤。
輸出格式：
第一行輸出不同的最短路徑的條數(shù)和能夠召集的最多的救援隊(duì)數(shù)量轮锥。第二行輸出從S到D的路徑中經(jīng)過的城市編號(hào)。數(shù)字間以空格分隔要尔，輸出首尾不能有多余空格交胚。

輸入樣例：
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
輸出樣例：
2 60
0 1 3

• 思路
  首先就是采用dijkstra算法，并且用優(yōu)先隊(duì)列來優(yōu)化盈电，便于最小dist的查找
  注意當(dāng)找到一條與當(dāng)前路徑長(zhǎng)度相等的新路時(shí)蝴簇，路的總條數(shù)并不是加1，而是加上到上一個(gè)點(diǎn)的路徑條數(shù)
  注意走到起點(diǎn)的路的條數(shù)要初始化為1

#include <iostream>
#include <queue>
#include <cstring>
#define INF 1000
#define N 510
using namespace std;
struct node {
    int num, val;

    friend bool operator<(node a, node b)
    {
        return a.val>b.val;
    }
};
int visited[N];
int dis[N];
int edge[N][N];
int numpeo[N];
int maxpeo[N];
int cur[N];//當(dāng)前最短路徑長(zhǎng)度
int pnum[N];//最大召集數(shù)情況下的上一個(gè)點(diǎn)
priority_queue<node> que;
int n, m, s, d;
void Dijkstra(int s, int t)
{
    cur[s] = 1;//注意這步的初始化不要漏
    pnum[s] = -1;//源點(diǎn)的上一個(gè)點(diǎn)匆帚，輸出路徑時(shí)會(huì)用到
    dis[s] = 0;
    node no;
    no.num = s;
    no.val = 0;
    que.push(no);
    //要訪問t的時(shí)說明能走到t的所有路徑都訪問過了
    while (!que.empty()) {
        while (visited[que.top().num]) que.pop();
        visited[que.top().num] = 1;
        if (que.top().num == t)
            break;
        for (int i = 0; i < n;++i)
            if ((!visited[i]) && edge[que.top().num][i]!=-1) {
                //注意此處循環(huán)到是也會(huì)跳過因?yàn)橐呀?jīng)visited過了
                //所以不用怕cur會(huì)因?yàn)檠h(huán)到自己了邊是0導(dǎo)致長(zhǎng)度相等而加1
                if (dis[i] == dis[que.top().num] + edge[que.top().num][i]) {
                    cur[i]+=cur[que.top().num];//注意此處并不是加1
                    if (maxpeo[i] < maxpeo[que.top().num] + numpeo[i]) {
                        maxpeo[i] = maxpeo[que.top().num] + numpeo[i];
                        pnum[i] = que.top().num;
                    }
                }
                if (dis[i] > dis[que.top().num] + edge[que.top().num][i]) {
                    dis[i] = dis[que.top().num] + edge[que.top().num][i];
                    cur[i] = cur[que.top().num];//注意這步并不是更新為1
                    pnum[i] = que.top().num;
                    maxpeo[i] = maxpeo[que.top().num] + numpeo[i];
                    no.num = i;
                    no.val = dis[i];
                    que.push(no);
                }
            }
        que.pop();
    }
}
int main()
{
    cin >> n >> m >> s >> d;
    memset(visited, 0, sizeof(visited));
    //調(diào)試的是后發(fā)現(xiàn)dis全被初始化成一個(gè)很大的負(fù)值
        //關(guān)于memset的問題在其他筆記里另寫
    memset(dis, 127, sizeof(dis));
    memset(edge, -1, sizeof(edge));
    memset(cur, 0, sizeof(cur));
    for (int i = 0; i < n; ++i) {
        cin >> numpeo[i];
        maxpeo[i] = numpeo[i];
        edge[i][i] = 0;
    }
    for (int i = 1; i <= m; ++i)
    {
        int start, end, length;
        cin >> start >> end >> length;
        edge[start][end] = edge[end][start] = length;
    }
    Dijkstra(s, d);
    cout << cur[d] << " " << maxpeo[d]<<endl;
    int p = d;
    int path[N];
    int num=-1;
    while (p!=-1) {
        ++num;
        path[num] = p;
        p = pnum[p];
    }
    for (int i = num; i >= 0; --i) {
        cout << path[i];
        if (i)
            cout << " ";
    }
    system("pause");
    return 0;
}