用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 算法或者 Floyd 算法来解决。

以下是使用 Dijkstra 算法的示例代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w;
    Edge(int _v, int _w) : v(_v), w(_w) {}
};

vector<Edge> g[50005];  // 邻接表存图
int tele[10];  // 存储发送消息的时间
int d[50005];  // 存储起点到每个点的最短距离
int pre[50005];  // 存储最短路径上每个节点的前驱节点
bool vis[50005];  // 记录每个节点是否已经被访问

// Dijkstra 算法
void dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    memset(d, INF, sizeof(d));
    memset(pre, -1, sizeof(pre));
    memset(vis, false, sizeof(vis));
    d[s] = 0;
    pq.push(make_pair(d[s], s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].v;
            int w = g[u][i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pre[v] = u;
                pq.push(make_pair(d[v], v));
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < 10; i++) {
        cin >> tele[i];
    }
    for (int i = 1; i <= n; i++) {
        int tele_num;
        cin >> tele_num;
        string str;
        cin >> str;
        for (int j = 0; j < str.size(); j++) {
            g[tele_num].push_back(Edge(str[j] - '0' + 1 + tele_num, tele[str[j] - '0']));
        }
    }
    int s, t;
    cin >> s >> t;
    dijkstra(s);
    if (d[t] == INF) {
        cout << "-1" << endl;
    } else {
        cout << d[t] << endl;
        vector<int> path;
        int cur = t;
        while (cur != -1) {
            path.push_back(cur);
            cur = pre[cur];
        }
        reverse(path.begin(), path.end());
        cout << path.size() << endl;
        for (int i = 0; i < path.size(); i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

时间复杂度为 O(nlogn)，可以通过本题。