https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805073643683840&page=0

const int MAX = 1e5 + 10;
const int inf = 1e9 + 7;

int n, m, st, ed;
int val[MAX];//节点权值
int mp[2010][2010];//最短路径
int dis[MAX], num[MAX], tot[MAX], vis[MAX];//dis与起点距离，num与起点的路径的最短路径权值和最大值，tot最短路径条数
int fa[MAX];


void dijkstra(int x)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++) tot[i] = 0;
    tot[x] = 1;
    for (int i = 0; i < n; i++) dis[i] = inf;
    dis[x] = 0;
    for (int i = 0; i < n; i++) 
    {
        int minn = inf;
        int pos = -1;
        for (int j = 0; j < n; j++) 
        {
            if (vis[j] == 0 && dis[j] < minn) 
            {
                minn = dis[j];
                pos = j;
            }
        }
        vis[pos] = 1;

        for (int j = 0; j < n; j++) 
        {
            if (j == pos)   continue;
            if (dis[pos] + mp[pos][j] == dis[j]) 
            {

                tot[j] += tot[pos];
                if (num[pos] + val[j] > num[j])
                {
                    fa[j] = pos;
                    num[j] = num[pos] + val[j];
                }

            }
            else if (dis[pos] + mp[pos][j] < dis[j]) 
            {
                tot[j] = tot[pos];
                fa[j] = pos;
                num[j] = num[pos] + val[j];
                dis[j] = dis[pos] + mp[pos][j];
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> st >> ed;
    for (int i = 0; i < n; i++) 
    {
        cin >> val[i];
        num[i] = val[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) 
        {
            mp[i][j] = inf;
        }
    }
    for (int i = 0; i < m; i++) 
    {
        int x, y, v;

        cin >> x >> y >> v;

        mp[x][y] = mp[y][x] = v;
    }
    for (int i = 0; i < n; i++) mp[i][i] = 0;
    dijkstra(st);
    cout << tot[ed] << " " << num[ed] << '\n';
    deque<int> q;
    int d = ed;
    while (1)
    {
        q.push_front(d);
        if (d == st) break;
        d = fa[d];
    }
    while (q.size())
    {
        cout << q.front();
        q.pop_front();
        if (q.size()) cout << " ";
    }

}