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

以下是该问题的C++代码实现，采用Dijkstra最短路径算法：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 50010;
const int MAXM = 100010;
const int INF = 0x3f3f3f3f;

int n, m;
int w[10];
int tele[MAXN];
vector<int> G[MAXN];

struct Node {
    int id, d;
    bool operator < (const Node &rhs) const {
        return d > rhs.d;
    }
};

int d[MAXN], vis[MAXN], pre[MAXN];

void dijkstra(int s) {
    memset(d, INF, sizeof(d));
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    priority_queue<Node> pq;
    d[s] = 0;
    pq.push({s, 0});
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        if (vis[u.id]) continue;
        vis[u.id] = 1;
        for (int i = 0; i < G[u.id].size(); i++) {
            int v = G[u.id][i];
            if (d[v] > d[u.id] + w[abs(tele[v] % 10 - tele[u.id] % 10)] + 1) {
                d[v] = d[u.id] + w[abs(tele[v] % 10 - tele[u.id] % 10)] + 1;
                pre[v] = u.id;
                pq.push({v, d[v]});
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < 10; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tele[i]);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dijkstra(1);
    if (d[n] == INF) {
        printf("-1\n");
    } else {
        printf("%d\n", d[n]);
        vector<int> ans;
        int u = n;
        while (u != -1) {
            ans.push_back(u);
            u = pre[u];
        }
        printf("%d\n", (int)ans.size());
        for (int i = ans.size() - 1; i >= 0; i--) {
            printf("%d ", ans[i]);
        }
    }
    return 0;
}

其中，G[i]表示第i个电报机可以直接到达的电报机的编号集合；d[i]表示从起点到第i个电报机的最短时间；pre[i]表示在最短路径中，第i个电报机的前一个电报机的编号。