Submission

Score: 100

User: Few500

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

Language: cpp

Time: 0.009 second

Submitted On: 2026-03-25 07:56:10

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<vector<int>> neighbors(n + 1);

    int car = 0;
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        neighbors[x].push_back(y);
        neighbors[y].push_back(x);
        if((x == 1 && y == n) || (x == n && y == 1))
            car = 1;
    }

    if(car == 1){
        for(int i=1; i<=n; i++){
            vector<int> road(n+1, 1);
            for(auto x : neighbors[i])
                road[x] = 0;
            neighbors[i] = {};
            for(int j=1; j<road.size(); j++)
                if(road[j])
                    neighbors[i].push_back(j);
        }
    }

    queue<int> q;
    q.push(1);
    vector<int> parent(n + 1, 0);
    vector<int> visited(n + 1, 0);
    visited[1] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(u == n) break;
        for(auto v : neighbors[u]){
            if(visited[v]) continue;
            visited[v] = 1;
            parent[v] = u;
            q.push(v);
        }
    }

    int ans = 0;
    for(int curr = n; curr != 1; curr = parent[curr]){
        if(curr == 0)
            return cout << -1, 0;
        ans += abs(curr - parent[curr]);
    }
    cout << ans * 10;
    return 0;
}