重返天梯-L3-011 直捣黄龙 (30 分)(dijkstra)

题目解析

重返天梯-L3-011 直捣黄龙 (30 分)(dijkstra)原题链接
本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。

写这道题之前，可以也写一写L2-001 紧急救援 (25 分)，都是比较基础的最短路径问题。不过这两道题除了要算出最短路径外，还要额外地输出一些参数。现在逐一对这些参数进行分析。

1. 最短路径条数。当要更新距离时，num[j] = num[t]；当距离相同时，num[j] += num[t]
2. 最短路径经过了哪些点。path[j] = t。记录前一个结点，最后倒序输出
3. 经过了多少个点，所经过的点中权重最大。w[j] = w[t] + 1或者a[j]

C++

#include 
#include 
#include 
using namespace std;
const int N = 210;
int n, k;
string sta, ed;
map<string, int> m; // 名称转编号
map<int, string> mis; // 编号转名称
int enemy[N]; 
int g[N][N];
int dist[N], num[N]; // 最短距离，最短路径条数
int w[N]; // 记录到当前点消灭了多少敌军
int city[N]; // 记录已经解放的城镇数
bool st[N]; // 标记最短路径已访问
int path[N]; // 记录前驱结点void PrintPath(int v) {if (v == 1) {cout << mis[1];return;}PrintPath(path[v]);cout << "->" << mis[v];
}void dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0, num[1] = 1, city[1] = 1;for (int i = 0; i < n; i++) {int t = -1;for (int j = 1; j <= n; j++) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;st[t] = true;for (int j = 1; j <= n; j++) {// 以最快的速度占领敌方大本营if (dist[j] > dist[t] + g[t][j]) {dist[j] = dist[t] + g[t][j];num[j] = num[t];path[j] = t;city[j] = city[t] + 1;w[j] = w[t] + enemy[j];} else if (dist[j] == dist[t] + g[t][j]) { // 当这样的路径不唯一时num[j] += num[t];if (city[j] < city[t] + 1) { // 要求选择可以沿途解放最多城镇的路径path[j] = t;city[j] = city[t] + 1;w[j] = w[t] + enemy[j];} else if (city[j] == city[t] + 1 && w[j] < w[t] + enemy[j]) {// 若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径path[j] = t;w[j] = w[t] + enemy[j];}}}}
}int main() {memset(g, 0x3f, sizeof g);cin >> n >> k >> sta >> ed;m[sta] = 1, m[ed] = 2;mis[1] = sta, mis[2] = ed;int idx = 3;for (int i = 0; i < n - 1; i++) {string str;int e;cin >> str >> e;if (!m.count(str)) {m[str] = idx;mis[idx] = str;idx++;}enemy[m[str]] = e;}while (k--) {string s1, s2;int v;cin >> s1 >> s2 >> v;int x = m[s1], y = m[s2];g[x][y] = v, g[y][x] = v;}dijkstra();PrintPath(2);puts("");printf("%d %d %d\n", num[2], dist[2], w[2]);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！