用c++解决Input The first line contains the number n of fighters in the division (2 ≤ n ≤ 50000). The second line contains ten integers in the range from 1 to 10000 separated with a space written in the nonascending order. These are the times of sending a message from one telegraph to another if the length of their common prefix is zero, one, two, …, nine. The next n lines contain the numbers of telegraphs given to the fighters of the division. The number of Anka's telegraph is described first, and the number of Chapaev's telegraph is described last. All the numbers of telegraphs are different. Output Output the only line “-1” if it is impossible to deliver the message to Chapaev. Otherwise, in the first line output the minimal time required to deliver the message. In the second line output the number of fighters in the delivery path, and in the third line output their numbers separated with a space in the order from Anka to Chapaev. The fighters of the 25th Division are numbered from 1 to n in the order in which their mobile telegraphs are described in the input. If there are several ways to deliver the message in minimal time, output any of them.
时间: 2024-02-04 19:04:08 浏览: 24
下面是使用Dijkstra算法解决该问题的C++代码实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 50005;
const int MAXM = 405;
struct Edge {
int to, w;
Edge(int t, int ww) : to(t), w(ww) {}
};
int n, s, t;
int tele[MAXN], d[MAXN], pre[MAXN];
vector<Edge> adj[MAXN];
int cost[MAXM][MAXM];
bool vis[MAXN];
void dijkstra() {
memset(d, INF, sizeof(d));
memset(pre, -1, sizeof(pre));
memset(vis, false, sizeof(vis));
d[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, s});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (Edge e : adj[u]) {
int v = e.to, w = e.w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.push({d[v], v});
pre[v] = u;
}
}
}
}
void print_path(int u) {
if (u != s) print_path(pre[u]);
cout << u << " ";
}
int main() {
cin >> n;
for (int i = 0; i < 10; i++)
cin >> cost[i][0];
for (int j = 1; j < 10; j++)
for (int i = j; i < 10; i++)
cost[i][j] = cost[i - 1][j - 1];
for (int i = 1; i <= n; i++)
cin >> tele[i];
s = tele[1], t = tele[n];
for (int i = 1; i < n; i++) {
int u = tele[i], v = tele[i + 1];
for (int j = 0; j < 4; j++) {
int w = cost[(u / (int) pow(10, j)) % 10][(v / (int) pow(10, j)) % 10];
adj[u].push_back(Edge(v, w));
adj[v].push_back(Edge(u, w));
}
}
dijkstra();
if (d[t] == INF) {
cout << "-1" << endl;
} else {
cout << d[t] << endl;
int cnt = 1;
int u = t;
while (u != s) {
cnt++;
u = pre[u];
}
cout << cnt << endl;
print_path(t);
}
return 0;
}
```
该代码首先读入输入,并将给定的十个数字存储在二维数组cost中,表示两个电报之间的通信时间。然后,根据给定的电报编号构建图,并使用Dijkstra算法求解从Anka到Chapaev的最短路径。
在输出路径时,可以使用一个pre数组记录路径中每个节点的前一个节点,然后从终点往回遍历,输出路径上的节点编号即可。
注:本题中的电报编号是按照给定顺序从1到n进行编号的,因此不需要进行映射。如果电报编号是一个任意的字符串,可以考虑使用哈希表或者字符串映射来处理。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![crx](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![crx](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![.zip](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)