用c++解决Time limit: 3.0 second Memory limit: 64 MB. 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 20:03:58 浏览: 32
下面是完整的 C++ 代码,实现了上述算法:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 50010;
const int MAXM = 500010;
int n;
int dist[MAXN], pre[MAXN];
int head[MAXN], ver[MAXM], edge[MAXM], nxt[MAXM], tot;
// 添加一条边
void add(int a, int b, int c) {
ver[++tot] = b;
edge[tot] = c;
nxt[tot] = head[a];
head[a] = tot;
}
// Dijkstra 算法求最短路径
void dijkstra(int s, int t) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
memset(dist, INF, sizeof(dist));
memset(pre, -1, sizeof(pre));
dist[s] = 0;
q.push(make_pair(0, s));
while (!q.empty()) {
int x = q.top().second;
q.pop();
if (x == t) {
return;
}
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
int z = edge[i];
if (dist[y] > dist[x] + z) {
dist[y] = dist[x] + z;
pre[y] = x;
q.push(make_pair(dist[y], y));
}
}
}
}
int main() {
cin >> n;
int w[10];
for (int i = 0; i < 10; i++) {
cin >> w[i];
}
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
string s = to_string(x);
int len = s.length();
for (int j = 0; j < len; j++) {
int y = stoi(s.substr(0, j+1));
for (int k = 0; k < 10; k++) {
if (k != s[j] - '0') {
int z = w[k];
add(y*10+k, x*10+s[j]-'0', z);
}
}
}
}
int s = 1, t = n*10+9;
dijkstra(s, t);
if (dist[t] == INF) {
cout << "-1" << endl;
} else {
vector<int> path;
for (int i = t; i != -1; i = pre[i]) {
path.push_back(i);
}
reverse(path.begin(), path.end());
int len = path.size();
cout << dist[t] << endl;
cout << len << endl;
for (int i = 0; i < len; i++) {
cout << path[i]/10 << " ";
}
cout << endl;
}
return 0;
}
```
代码解释:
1.首先读入数据,包括每个电报的编号和相邻电报之间的传输时间。
2.然后根据每个电报的编号构建图,对于每个电报,根据其编号构建所有可能的后继节点,并连接边,并给每条边赋上对应的权值。
3.使用 Dijkstra 算法求出从 Anka 的节点到 Chapaev 的节点的最短路径。
4.如果不存在这样的路径,则输出 -1。否则,输出最短路径的长度和路径中所有电报的编号。
注意事项:
1.在构建图时,我们需要将每个电报的编号乘以 10,然后加上其后继节点的编号,以避免编号拼接时出现错误。
2.在输出路径时,需要将每个电报的编号除以 10,以得到其在原始输入中的编号。
3.如果存在多条最短路径,输出任意一条即可。