Submission

Score: 100

User: C12

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

Language: cpp

Time: 0.011 second

Submitted On: 2026-01-09 11:08:30

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

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define ll long long
#define ull unsigned long long
#define mp make_pair
 
#define mpiii(a,b,c) make_pair(a,make_pair(b,c));
ll mod = 1000000007;

void solve(){
    ll n,m;
    ll p,q;
    
    cin >> n >> m;

    vector<vector<ll>>adj(n + 1);

    for(int i = 0;i < m;i++){
        cin >> p >> q;
        adj[p].push_back(q);
        adj[q].push_back(p);
    }

    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
    pq.push(mp(0,1));
    ll train_time = 0;
    pair<ll,ll> t;

    vector<bool>check_1(n+1, false),check_2(n+1, false);

    while(!pq.empty()){
        t = pq.top();
        pq.pop();

        if(check_1[t.second] == 1) continue;
        check_1[t.second] = 1;

        if(t.first > n*n){
            train_time = -1;
            break;
        }

        for(auto x: adj[t.second]){
            pq.push(mp(t.first + abs(t.second - x),x));
            if(x == n){
                train_time = t.first + abs(t.second - x);
                break;
            }
        }

        if(train_time > 0) break;
        if(train_time < 0) break;
    }

    if(train_time <= 0) {
        cout << -1;
        return;
    }

    while(!pq.empty()) pq.pop();
    pq.push(mp(0,1));
    ll car_time = 0;

    ll j,now;
    while(!pq.empty()){
        t = pq.top();
        pq.pop();

        if(check_2[t.second] == 1) continue;
        check_2[t.second] = 1;

        if(t.first > n*(n-1)/4){
            car_time = -1;
            break;
        }

        j = 0;
        
        sort(adj[t.second].begin(),adj[t.second].end());

        now = adj[t.second][j];
        
        for(int i = 1;i <= n;i++){
            // cout << now << '\n';
            if(t.second == i) continue;

            if(i == now) { 
                // cout << j << ' ' << adj[t.second].size() << '\n';
                j++;
                if(j < adj[t.second].size()){
                    now = adj[t.second][j];
                }    
                continue; 
            }
            
            pq.push(mp(t.first + abs(t.second - i),i));
            if(i == n){
                car_time = t.first + abs(t.second - i);
                break;
            }
        }
        // cout << '\n';

        if(car_time > 0) break;
        if(car_time < 0) break;
    }
    if(car_time <= 0) {
        cout << -1;
        return;
    }

    // cout << car_time << ' ' << train_time << ' ';

    cout << (max(car_time,train_time) * 10);

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

    ll q;
 
    // cin >> q;

    // while(q--) 
    
    solve();

    return 0;
}