#include<algorithm> #include<iostream> #include<vector> #include<string> #include<cmath> #include <cstdio> #include <map> #include <unordered_map> using namespace std; const int INF = 0x3f3f3f3f; int n, gamma, time_count=0; int time[10]; string alpha; vector<int> Length(50005, 0); unordered_map<string, int> number; unordered_map<int, string> nega_number; vector<unordered_map<int, int>> edge(50005); vector<int> trace(50005, 0); vector<int> final_trace; void finding(string alpha) { int a=number[alpha], b; char beta; string epsilon; for(int i=9; i>=0; i--) { for(int j=1; j<10; j++) { epsilon = alpha; epsilon[i] = '0' + (int(epsilon[i]) + j) % 10; if(number.find(epsilon) != number.end() and epsilon != alpha) { b = number[epsilon]; edge[a][b]= time[i]; } } for(int j=i-1; j>=0; j--) { epsilon = alpha; beta = epsilon[j]; epsilon[j] = epsilon[i]; epsilon[i] = beta; if(number.find(epsilon) != number.end() and epsilon != alpha) { b = number[epsilon]; edge[a][b]= time[j]; } } } } void dijkstra(int i) { int beta; for(auto j : edge[i]) { beta = Length[j.first]; if(beta > Length[i] + j.second) { Length[j.first] = Length[i] + j.second; trace[j.first] = i; if(beta == INF) { dijkstra(j.first); } } } } int main() { cin>>n; for(int i=2; i<n+1;i++) { Length[i] = INF; } for(int i=0; i<10; i++) { cin>>time[i]; } for(int i=0; i<n; i++) { cin>>alpha; nega_number[i] = alpha; number[alpha] = i+1; } for(int i=0; i<n; i++) { alpha = nega_number[i]; finding(alpha); } dijkstra(1); if(Length[n] == INF) { cout<<"-1"; } else { gamma = n; final_trace.push_back(gamma); cout<<Length[n]<<endl; while(gamma != 1) { gamma = trace[gamma]; final_trace.push_back(gamma); } cout<<final_trace.size()<<endl; for(int i=final_trace.size()-1;i>-1;i--) { cout<<final_trace[i]<<" "; } } //system("pause"); return 0; }修改当中的dijkstra

在这份代码中，我们可以发现`dijkstra`函数实现的是单源最短路径算法，其核心思想是不断更新起点到各个顶点之间的最短路径。下面是修改后的`dijkstra`函数代码：

void dijkstra(int i) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    vector<bool> vis(n+1, false);
    q.push({0, i});
    Length[i] = 0;

    while(!q.empty()) {
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;

        for(auto j : edge[u]) {
            int v = j.first, w = j.second;
            if(Length[v] > Length[u] + w) {
                Length[v] = Length[u] + w;
                trace[v] = u;
                q.push({Length[v], v});
            }
        }
    }
}

在这份代码中，我们使用了优先队列来维护当前未确定最短路径的顶点，每次取出距离最小的顶点进行松弛操作。我们同时使用了一个vector来记录每个顶点是否已经被确定最短路径，以避免重复遍历。需要注意的是，我们在初始化时将起点的最短路径长度设为0，其余顶点的最短路径长度设为正无穷，这样可以保证起点首先被加入队列。

另外，我们在这段代码中还省略了一些之前的变量声明和输入输出操作，需要根据实际情况进行补充。