K-太空电梯 题解

典型 dijkstra 细节在于电梯的移动过程

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10;

int n, k, tim[N];
bool st[N];

vector<vector<int> > v;
 
int bfs()
{
    memset (tim, 0x3f, sizeof (tim));
    tim[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({tim[1], 1});
    
    
    while (q.size() != 0){
        
        int x = q.top().first, y = q.top().second;
        q.pop();
        
        if (st[y] == true) continue;

        st[y] = true;
        for (int i = 0; i < v[y].size(); i ++ ){
            int p = v[y][i];
                
                int a = tim[y] % (2 * abs (y - p));
                int b = abs (p - y);
                int ans = 0;
                
                if (y > p){
                    if (a == b){
                        ans = b;
                    }
                    else if (a > b) {
                        ans = 4 * b - a;
                    }
                    else{
                        ans = 2 * b - a;
                    }
                }
                else{
                    if (a == 0){
                        ans = b;
                    }
                    else if (a > b){
                        ans = 3 * b - a;
                    }
                    else if (a <= b){
                        ans = 3 * b - a;
                    }
                }
                
                tim[p] = min(tim[p], ans + tim[y]);
                
                if (p != n){
                    q.push({tim[p], p});
                }  
        }
    }
    
    return tim[n];
}

signed main(void)
{
    cin >> n >> k;
    
    v.resize(n + 1);
    
    for (int i = 0; i < k; i ++ ){
        int a, b; cin >> a >> b;
        
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    cout << bfs() * 5 << endl;
 
    return 0;
}