题目链接：PTA-紧急救援

题意：

n点，m边的无向图，每个点有一个点权，求从st到ed的最短路条数，并输出点权和最大的一条最短路，输出权值和路径。

题解：

更新点权时类似于最短路更新。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 600;
const int MAXM = 500 * 500;
const int inf = 0x3f3f3f3f;
int n, m, st, ed;
int val[MAXN], ans[MAXN];
struct EDGE
{
    int v, w, nxt;
} edge[MAXM];
int cnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
struct node
{
    int u;
    int d;
    node(int u, int d) : u(u), d(d) {}
    bool operator<(const node &a) const
    {
        return d > a.d;
    }
};
bool used[MAXN];
int dis[MAXN], CNT[MAXN], pre[MAXN];
void dijkstra(int st)
{
    priority_queue<node> que;
    while (!que.empty())
        que.pop();
    memset(dis, inf, sizeof(dis));
    memset(CNT, 0, sizeof(CNT));
    memset(pre, -1, sizeof(pre));
    dis[st] = 0;
    CNT[st] = 1;
    ans[st] = val[st];
    que.push(node(st, dis[st]));
    memset(used, 0, sizeof(used));
    while (!que.empty())
    {
        int u = que.top().u;
        que.pop();
        if (used[u])
            continue;
        used[u] = 1;
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (used[v])
                continue;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                CNT[v] = CNT[u];
                ans[v] = ans[u] + val[v];
                pre[v]=u;
                que.push(node(v, dis[v]));
            }
            else if (dis[v] == dis[u] + w)
            {
                CNT[v] += CNT[u]; //记录最短路数
                if(ans[v]<ans[u]+val[v])
                {
                    ans[v]=ans[u]+val[v];
                    pre[v]=u;
                }    
            }    
        }
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &st, &ed);
    memset(fir, -1, sizeof(fir));
    for (int i = 0; i < n; i++)
        scanf("%d", &val[i]);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    dijkstra(st);
    printf("%d %d\n", CNT[ed], ans[ed]);
    int temp=ed;
    vector<int>    a;
    a.clear();
    while(pre[temp]!=-1)
    {
        a.push_back(temp);
        temp=pre[temp];
    }
    a.push_back(st);
    for(int i=a.size()-1;i>0;i--)
        printf("%d ",a[i]);
    printf("%d",a[0]);
    return 0;
}