题意：
n个城市m条路，每个城市有救援小组，所有的边的边权已知。给定起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权（城市救援小组数目）最大的那个
思路：
我自己做的是先求出最短路径，再从终点往前递归，将所有救援小组数目存入vector，最后取最大值输出即可，思路倒是清晰但是感觉还是差了点。
#include<string>
#include<cstdlib>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#define INF 0x3f3f3f
using namespace std;
const int maxn = 510;
int road[maxn][maxn];
bool vis[maxn];
int dis[maxn];
int n, m;
int num[maxn];
int s, e;
vector<int> numMax;
void dijkstra(int s) {
int i, j, temp, min;
int max = -1;
memset(vis, true, sizeof(vis));
vis[s] = false;
for (i = 0; i < n; i++) {
dis[i] = road[s][i];
}
dis[s] = 0;
for (i = 0; i < n; i++) {
min = INF;
for (j = 0; j < n; j++) {
if (vis[j] && min > dis[j]) {
temp = j;
min = dis[j];
}
}
vis[temp] = false;
for (j = 0; j < n; j++) {
if (vis[j] && road[temp][j] + dis[temp] <= dis[j]) {
dis[j] = road[temp][j] + dis[temp];
}
}
}
}
void result(int res, int pos, int sum) {
if (pos == s) {
numMax.push_back(sum);
return;
}
for (int i = 0; i < n; i++) {
if (dis[i] + road[i][pos] == res) {
//printf("%d %d %d\n", dis[i], i, sum+num[i]);
result(dis[i], i, sum + num[i]);
}
}
}
int main() {
int x, y, z;
while (scanf("%d%d", &n, &m) != EOF) {
scanf("%d%d", &s, &e);
for (int i = 0; i < n; i++)
scanf("%d", &num[i]);
memset(road, INF, sizeof(road));
while (m--) {
scanf("%d%d%d", &x, &y, &z);
if (z<road[x][y])
road[x][y] = road[y][x] = z;
}
dijkstra(s);
result(dis[e], e, num[e]);
int max = -1;
for (auto x : numMax) {
if (max < x)
max = x;
}
cout << numMax.size() << " " << max << endl;
}
return 0;
}
网上的代码思路是在dijkstra的同时用dp，也就是处理松弛的情况时，维护way和w数组，分别表示路径数与救援队数，当同样是最短路径时，way[v]=sum(way[u])，这里有简单的动态规划的思想。
#include<string>
#include<cstdlib>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
const int maxn = 510;
const int inf = 9999999;
int n, m;
int edge[maxn][maxn], weight[maxn], dis[maxn];
bool vis[maxn];
int way[maxn], w[maxn];//way是起点到i节点的路径数
int s, e; //w是起点到i节点救援队总和
void dijkstra(int s) {
fill(dis, dis + maxn, inf);
fill(vis, vis + maxn, true);
dis[s] = 0;
w[s] = weight[s];
way[s] = 1;
for (int i = 0; i < n; i++) {
int u = -1, min = inf;
for (int j = 0; j < n; j++) {
if (vis[j] && min > dis[j]) {
u = j;
min = dis[j];
}
}
if (u == -1) break;
vis[u] = false;
for (int v = 0; v < n; v++) {
if (vis[v] && edge[u][v] != inf) {
if (dis[u] + edge[u][v] < dis[v]) {
way[v] = way[u]; //此时v的路径数与u相同
dis[v] = dis[u] + edge[u][v];
w[v] = w[u] + weight[v];
}
else if (dis[u] + edge[u][v] == dis[v]) {
way[v] += way[u]; //此时v的路径数加上u的路径数
if (w[u] + weight[v] > w[v])
w[v] = w[u] + weight[v];
}
}
}
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &e);
for (int i = 0; i < n; i++)
scanf("%d", &weight[i]);
fill(edge[0], edge[0] + maxn*maxn, inf);
int a, b, c;
while (m--) {
scanf("%d%d%d", &a, &b, &c);
edge[a][b] = edge[b][a] = c;
}
dijkstra(s);
printf("%d %d", way[e], w[e]);
return 0;
}