Submission

Score: 100

User: C12

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

Language: cpp

Time: 0.010 second

Submitted On: 2026-03-19 21:59:32

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;
#define ll long long
#define pii pair<ll,int>

int adj_matrix[401][401];

ll dist_train[401];
ll dist_car[401];

int vis_train[401];
int vis_car[401];

vector<int> adj_train[401];
vector<int> adj_car[401];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;

    cin >> n >> m;

    int u,v,w;
    for(int i = 0;i < m;i++){
        cin >> u >> v;

        if(u > v) swap(u,v);
        adj_matrix[u][v] = 1;
    }

    for(int i = 1;i <= n;i++){
        dist_car[i] = INT_MAX;
        dist_train[i] = INT_MAX;
        for(int j = 1;j < i;j++){
            if(adj_matrix[j][i] == 0){
                adj_car[i].push_back(j);
                adj_car[j].push_back(i);
            }
            else{
                adj_train[i].push_back(j);
                adj_train[j].push_back(i);
            }
        }
    }

    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,1});
    dist_car[1] = 0;
    dist_train[1] = 0;

    while (!pq.empty())
    {
        ll u = pq.top().second;
        // cerr << "train" << ' ' << u << '\n';
        pq.pop();
        if(vis_train[u]) continue;
        vis_train[u] = 1;

        if(u == n) break;

        for(ll v : adj_train[u]){
            if(dist_train[v] > dist_train[u] + (abs(u-v))){
                dist_train[v] = dist_train[u] + (abs(u-v));
                pq.push({dist_train[v],v});
            }
        }
    }

    while (!pq.empty()) pq.pop();
    
    pq.push({0,1});

    while (!pq.empty())
    {
        ll u = pq.top().second;
        // cerr << "car" << ' ' << u << '\n';
        pq.pop();
        if(vis_car[u]) continue;
        vis_car[u] = 1;

        if(u == n) break;

        for(ll v : adj_car[u]){
            if(dist_car[v] > dist_car[u] + (abs(u-v))){
                dist_car[v] = dist_car[u] + (abs(u-v));
                pq.push({dist_car[v],v});
            }
        }
    }

    if(!vis_car[n] || !vis_train[n]){
        cout << -1;
    }
    else{
        cout << max(dist_car[n],dist_train[n])*10LL;
    }

    return 0;
}