22年真题优化dijkstra改编

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510, M = 1e5 + 10, INF = 0x3f3f3f3f;
int dis[N], g[N][N], num[N], pa[N], se[N];
int n, m, cnt, c1, c2;
bool st[N];

void Dijkstra(int c1, int c2)
{
    memset(dis, INF, sizeof dis);
    dis[c1] = 0; pa[c1] = 1, se[c1] = num[c1]; 
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 0; j < n; j ++)
        {
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        }
        st[t] = true;
        for(int j = 0; j < n; j ++)
        {
            if (!st[j] && dis[j] > dis[t] + g[t][j]) 
            {
                dis[j] = dis[t] + g[t][j];
                pa[j] = pa[t];
                se[j] = se[t] + num[j];
            }
            else if (!st[j] && dis[j] == dis[t] + g[t][j]) // st[j] 会保持所有最小路径都被遍历出来他才会设为true
            { // 在这之前 se[j] 会更新成最大值，因为所有到j的最小路径都遍历过了
                pa[j] += pa[t];
                se[j] = max(se[j], se[t] + num[j]);
            }
        }
    }
}

int main()
{
    cin >> n >> m >> c1 >> c2;
    memset(g, INF, sizeof g);
    for (int i = 0; i < n; i ++ ) cin >> num[i];
    for(int i = 0; i < m; i ++)
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        g[x][y] = g[y][x] = min(g[x][y], w);
    }
    Dijkstra(c1, c2);
    cout << pa[c2] << ' ' << se[c2] << endl;
    return 0;
}