题目链接：https://www.patest.cn/contests/pat-a-practise/1003
题意，给我们n个点，有m条路，每个点都有一个权值，每一条路都有自己的长度且都是双向的路，让我们求从起点s，到终点e之间的最短路径数量，且求出在这些最短路程中所有点权值和最大的一条的权值和。
仔细分析，这题应该是最短路径的变形题目(如果最短路不熟练的同学可以出门左转先去学习最短路:传送门)，首先求权值和最大的一条的方法很容易，只需要在路径长度上再加一个权值和作为第二个比较条件，比较容易。
那么关键问题是如何去求这个最短路径数。这里小编用到的方法是用一个num数组记录s到当前点的最短路径的数量，当我们在更新最短路时，如果前一个点a到当前点b的路径比当前到b的路径短，那么num[b] = num[a]，如果从a到b的路径等于到当前b的最短路径，那么num[b] += num[a]，在每一次更新之后就将前点的num清零，避免重复更新。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 505;
int mp[maxn][maxn];
int num[maxn], dis[maxn], sum[maxn];
int val[maxn];
int s, e, n;
struct Edge{int v, w, next;
}edge[maxn*maxn];
int head[maxn], tot;
void init() {tot = 0;memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w) {edge[tot].v = v;edge[tot].w = w;edge[tot].next = head[u];head[u] = tot++;
}
void SPFA()
{ queue<int> q; q.push(s); memset(num,0,sizeof(num)); memset(dis,INF,sizeof(dis)); memset(sum,0,sizeof(sum));dis[s] = 0; sum[s] = val[s]; num[s] = 1; int u,v,w; while(!q.empty()) { u = q.front();q.pop(); if(u == e) continue;for(int i=head[u]; i!=-1; i=edge[i].next) {v = edge[i].v;w = edge[i].w;if(dis[v] > dis[u]+w) { dis[v] = dis[u]+w; sum[v] = sum[u]+val[v]; if(!num[v]) q.push(v); num[v] = num[u]; } else if(dis[v] == dis[u]+w) { sum[v] = max(sum[u]+val[v],sum[v]); if(!num[v]) q.push(v); num[v] += num[u]; } } num[u] = 0; }
} int main()
{int m, u, v, w; scanf("%d%d%d%d",&n, &m, &s, &e);init();for(int i = 0; i < n; ++i) {scanf("%d",&val[i]); }memset(mp,INF,sizeof(mp));while(m--) { scanf("%d%d%d",&u, &v, &w);addEdge(u, v, w);addEdge(v, u, w); }SPFA(); printf("%d %d\n",num[e], sum[e]);return 0;
}