Submission

Score: 0

User: Gump2011

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-08 14:54:36

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    bool rail[405][405] = {0};

    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        rail[u][v] = rail[v][u] = 1;
    }

    long long dist[405][405];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dist[i][j] = INF;

    priority_queue<
        pair<long long,pair<int,int>>,
        vector<pair<long long,pair<int,int>>>,
        greater<pair<long long,pair<int,int>>>
    > pq;

    dist[1][1] = 0;
    pq.push({0,{1,1}});

    while(!pq.empty()){

        long long d = pq.top().first;
        int t = pq.top().second.first;
        int c = pq.top().second.second;
        pq.pop();

        if(d != dist[t][c]) continue;

        if(t==n && c==n){
            cout << d;
            return 0;
        }

        // train move
        for(int v=1;v<=n;v++){
            if(!rail[t][v]) continue;

            if(v==c && v!=n) continue;

            long long w = 10LL * abs(v-t);

            if(dist[v][c] > d + w){
                dist[v][c] = d + w;
                pq.push({dist[v][c],{v,c}});
            }
        }

        // car move
        for(int v=1;v<=n;v++){
            if(rail[c][v] || v==c) continue;

            if(v==t && v!=n) continue;

            long long w = 10LL * abs(v-c);

            if(dist[t][v] > d + w){
                dist[t][v] = d + w;
                pq.push({dist[t][v],{t,v}});
            }
        }
    }

    cout << -1;
}