Submission

Score: 100

User: solarsunny

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

Language: cpp

Time: 0.020 second

Submitted On: 2025-11-03 23:42:45

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n,m;
    cin >> n >> m;
    bool railroad[n][n];
    memset(railroad,false,sizeof(railroad));
    for(int i=0; i<m; i++) {
        int x,y;
        cin >> x >> y;
        
        railroad[x-1][y-1]=true;
        railroad[y-1][x-1]=true;
    }
    bool checkroad=railroad[0][n-1];
    vector<bool> explored(n);
    priority_queue<pair<int,int> > pq;
    pq.push(make_pair(0,0));
    while (pq.size() > 0)
    {
        int dist =  -pq.top().first;
        int node = pq.top().second;
        pq.pop();
        if(node == n-1) {
            cout << dist << "\n";
            return 0;
        }
        if(explored[node]) {
            continue;
        }
        explored[node] = true;
        for(int i=0; i<n; i++) {
            if(explored[i]) {
                continue;
            }
            if(railroad[node][i] != checkroad) {
                pq.push(make_pair(-(dist+10*(abs(i-node))),i));
            }
        }
    }
    cout << "-1\n";
    return 0;
}