Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Nathlol2

Problemset: รถยนต์ รถไฟ เรือเมล์ ลิเก ตำรวจ

Language: cpp

Time: 0.016 second

Submitted On: 2025-03-16 20:10:33

#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
using namespace std;
int solve(vector<vector<pii>> &g, int n){
    vector<int> dist(n + 1, 1e9);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if(d > dist[u]){
            continue;
        }
        for(auto [v, w] : g[u]){
            if(d + w < dist[v]){
                dist[v] = d + w;
                pq.push({d + w, v});
            }
        }
    }
    return dist[n];
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<pii>> g(n + 1), G(n + 1);
    vector<vector<int>> tr(n + 1, vector<int>(n + 1));
    int a, b;
    for(int i = 0;i<m;i++){
        cin >> a >> b;
        g[a].pb({b, 10 * abs(a - b)});
        g[b].pb({a, 10 * abs(a - b)});
        tr[a][b] = 1;
        tr[b][a] = 1;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(tr[i][j] == 0){
                G[i].pb({j, 10 * abs(i - j)});
            }
        }
    }
    int ans = max(solve(g, n), solve(G, n));
    if(ans == 1e9){
        cout << "-1\n";
    }else{
        cout << ans << '\n';
    }
}