点击刷新
题解
该题考察最短路问题，采用 dijkstra 算法，并在其基础上进行扩展。
首先是路径打印，需要记录该点具体由上一个（哪一个点）转移过来的，用 $path[]$ 数组记录（具体在更新循环中）。
如上图。
敲重点
关于如何求解路径条数和对应最短路径下的最多救援队数量，我们先看下图
设 $su[i]$ 表示从 $s$ （起点）到 $i$ 点最短距离救援队数量的最大值，$dist[i]$ 表示从 $s$ （起点）到 $i$ 点的最短距离，采用邻接矩阵 $g$ 存储所有的边，$num[i]$ 存储 $s$（起点）到 $i$ 点最短路径的条数。
满足 dist[j] <= dist[t] + g[t][j] 的情况下，我们分两种情况进行讨论
1、dist[j] == dist[t] + g[t][j]
>则距 j 点对应的最短距离是不变的，此时数量对其取 max 即可。
>路径很显然增加 num[t]（可由 t 扩展）。
2、dist[j] < dist[t] + g[t][j]
>则需更新最短距离，由此路径必定为经过 t 再经过由 t 到 j 的边，此时的数量更新为 su[t] + c[j]（c[j] 表示 j 点对应救援队的数量）。
>路径也必须更新至 t 对应的最短路径的条数。
记得初始 num[s] = 1，即自己到自己的一条路径。
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 510; int n, m, s, d, ans; int g[N][N], dist[N], c[N], path[N], num[N], p[N]; int su[N]; bool st[N]; void dijkstra() { memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; for (int i = 0; i < n; ++i) { int t = -1; for (int j = 0; j < n; ++j) { if (!st[j] && (t == -1 || dist[t] > dist[j])) { t = j; } } st[t] = true; for (int j = 0; j < n; ++j) { if (dist[j] >= dist[t] + g[t][j]) { if (dist[j] == dist[t] + g[t][j]) { num[j] += num[t]; if (su[j] < su[t] + c[j]) { su[j] = su[t] + c[j]; path[j] = t; } } else { num[j] = num[t]; su[j] = su[t] + c[j]; path[j] = t; dist[j] = dist[t] + g[t][j]; } } } } int last = d; while (last != s) { p[ans++] = last; last = path[last]; } p[ans++] = last; cout << num[d] << " " << su[d] << endl; for (int i = ans - 1; i >= 0; --i) { if (i == 0) { cout << p[i] << endl; } else { cout << p[i] << " "; } } } int main() { cin >> n >> m >> s >> d; memset(g, 0x3f, sizeof(g)); for (int i = 0; i < n; ++i) { // 城市救援队数量 cin >> c[i]; su[i] = c[i]; } for (int i = 0; i < m; ++i) { // 城市网络结构 int a, b, w; cin >> a >> b >> w; g[a][b] = g[b][a] = w; } // 因为由 s 点出发 num[s] = 1; dijkstra(); return 0; }
© 著作权归作者所有
举报
发表评论
0/200
