1003 Emergency (25)

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    //基本初始化
    const int inf = 99999999;
    int e[500][500] = {inf};//e表示两个城市之间是否有路径 以及该路径的长度  没有路径则其长度为inf
    fill(e[0], e[0] + 500*500, inf);
    int weight[500];//weight表示该座城市救援队的数量
    int dis[500] = {inf};//dis表示该座城市到源点的最短距离
    fill(dis, dis + 500, inf);
    int visited[500];//先将所有城市都设置为未访问
    fill(visited, visited + 500, 0);
    int pathn[500];//记录每个城市最短路径的数量
    fill(pathn, pathn + 500, 0);
    int w[500] = {0};//表示路径上所有救援队的最大数量
    fill(w, w + 500, 0);
    
    //输入数据
    int n, m, c1, c2;//城市数量  道路数量  源点 终点
    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for (int i = 0; i < n; i++) {//输入每座城市的救援队的数量
        scanf("%d", &weight[i]);
    }
    int a, b, c;
    for(int i = 0; i < m; i++) {//输入存在道路的城市及其路径长度
        scanf("%d%d%d", &a, &b, &c);
        e[a][b] = e[b][a] = c;
    }
    
    //初始化
    dis[c1] = 0;
    w[c1] = weight[c1];
    pathn[c1] = 1;
    
    //dijkstra
    for (int i = 0; i < n; i++) {
        //找出未收录定点中dist最小者
        int u = -1, minn = inf;
        for (int j = 0; j < n; j++) {
            if (visited[j] == 0 && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;//所有顶点都已收录
        visited[u] = true;//标记该点为已经收录
        
        for (int v = 0; v < n; v++) {
            if (visited[v] == 0 && e[u][v] != inf) {//向外拓展 如果一点未被访问且与刚才找出的dist最小的那个点之间存在路径
                if (dis[u] + e[u][v] < dis[v]) {//如果从刚才找到的dist最小那个点到拓展点的距离和 小与原该点到源点的距离 则更新这个点的路径
                    dis[v] = dis[u] + e[u][v];
                    pathn[v] = pathn[u];
                    w[v] = w[u] + weight[v];//这一条是求最大救援队的数量
                }else if(dis[u] + e[u][v] == dis[v]){// 如果相等 则证明存在两条最短路径
                    pathn[v] = pathn[v] + pathn[u];
                    if (w[u] + weight[v] > w[v]) {//求最大救援队的数量
                        w[v] = w[u] + weight[v];
                    }
                }
            }
        }
 
    }
    
    printf("%d %d\n", pathn[c2], w[c2]);
    
    return 0;
}