用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-01 21:04:36 浏览: 69
The King Of Fighters Wing EX v1.0 Setup.exe
以下是一个使用 Dijkstra 算法解决这个问题的 C++ 代码实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 50005;
const int MAXM = 10;
const int INF = 0x3f3f3f3f;
int n, t[MAXM + 1];
int s, t;
int dist[MAXN], path[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN], nodes;
void dijkstra() {
memset(dist, INF, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, s));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (!vis[v] && dist[v] > dist[u] + t[nodes[u]][nodes[v]]) {
dist[v] = dist[u] + t[nodes[u]][nodes[v]];
path[v] = u;
pq.push(make_pair(dist[v], v));
}
}
}
}
int main() {
cin >> n;
for (int i = 0; i < MAXM; i++) {
cin >> t[i];
}
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
nodes.push_back(x);
if (x == s) {
s = i;
}
if (x == t) {
t = i;
}
}
for (int u = 1; u <= n; u++) {
for (int v = u + 1; v <= n; v++) {
int len = 0;
while (len < MAXM && (nodes[u - 1] / (int)pow(10, len)) % 10 == (nodes[v - 1] / (int)pow(10, len)) % 10) {
len++;
}
adj[u].push_back(v);
adj[v].push_back(u);
t[len] = min(t[len], t[len - 1]);
}
}
dijkstra();
if (dist[t] == INF) {
cout << -1 << endl;
} else {
cout << dist[t] << endl;
vector<int> ans;
for (int u = t; u != s; u = path[u]) {
ans.push_back(nodes[u - 1]);
}
ans.push_back(nodes[s - 1]);
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
}
return 0;
}
```
在这个代码中,我们首先读入输入数据,并将每个电报看作一个节点。然后,我们通过比较两个电报的编号,计算它们的前缀长度,并根据前缀长度建立边。我们将边权设为两个电报之间发送信息的时间,根据题目要求,如果两个电报的前缀长度相同,则需要将这个时间设为它们前缀长度减一的时间,以保证时间的单调性。
接着,我们使用 Dijkstra 算法求解从起点到终点的最短路径。我们使用一个数组 path 存储最短路径上每个节点的前驱节点,最后可以通过回溯这个数组来找到最短路径。
最后,我们根据题目要求输出结果即可。如果无法到达终点,则输出 -1。否则,输出最短时间、最短路径上的节点数以及最短路径上的节点编号。注意,由于我们在建图时将节点编号从 1 开始计数,因此最后输出节点编号时需要将它们减一。
阅读全文