用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.

这道题目是一道图论题目，需要用到 Dijkstra 算法。我们可以将每个电报看作一个点，电报之间的时间看作边，构建一个加权有向图。然后以 Anka 的电报为起点，以 Chapaev 的电报为终点，运用 Dijkstra 算法求解最短路径。

具体地，我们可以使用一个数组 dist 存储从起点到每个点的最短距离，初始化为正无穷。同时，我们使用一个数组 vis 存储每个点是否已经被访问过，初始化为 false。然后，我们从起点开始，将 dist[起点] 设为 0，然后找到与起点直接相连的所有点，更新它们的 dist 值。接着，我们从未访问过的点中找到 dist 值最小的点，将其标记为已访问，并更新与它相连的所有点的 dist 值。重复这个过程，直到我们找到终点或者没有未访问过的点。

最后，如果 dist[终点] 为正无穷，则说明无法到达终点，输出 -1。否则，dist[终点] 就是最短时间。我们可以使用一个数组 path 存储 Anka 到 Chapaev 的最短路径上的点，然后从终点开始往前遍历这个数组，输出路径上的点的编号即可。

相关问题

用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.

下面是使用Dijkstra算法解决该问题的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进行编号的，因此不需要进行映射。如果电报编号是一个任意的字符串，可以考虑使用哈希表或者字符串映射来处理。

写一段Java实现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.

以下是Java实现，可以满足你的要求：

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] t = new int[10];
for (int i = 0; i < 10; i++) {
t[i] = sc.nextInt();
}
int[] telegraphs = new int[n];
for (int i = 0; i < n; i++) {
telegraphs[i] = sc.nextInt();
}
int anka = sc.nextInt();
int chapaev = sc.nextInt();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
boolean[] visited = new boolean[n];
dist[anka - 1] = 0;
int[] prev = new int[n];
Arrays.fill(prev, -1);
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a - 1] - dist[b - 1]);
pq.offer(anka);
while (!pq.isEmpty()) {
int u = pq.poll();
if (visited[u - 1]) {
continue;
}
visited[u - 1] = true;
for (int i = 0; i < n; i++) {
if (telegraphs[i] == u) {
for (int j = 0; j < 10; j++) {
int v = i + j + 1;
if (v > n || visited[v - 1]) {
continue;
}
int w = dist[u - 1] + t[j];
if (w < dist[v - 1]) {
dist[v - 1] = w;
prev[v - 1] = u;
pq.offer(v);
}
}
}
}
}
if (dist[chapaev - 1] == Integer.MAX_VALUE) {
System.out.println("-1");
} else {
System.out.println(dist[chapaev - 1]);
List<Integer> path = new ArrayList<>();
int cur = chapaev;
while (cur != -1) {
path.add(cur);
cur = prev[cur - 1];
}
Collections.reverse(path);
System.out.println(path.size());
for (int i : path) {
System.out.print(i + " ");
}
}
}
}