Submission

[PPPPPPPPPPPPPPPPP-SS]

Score: 0

User: yumiKuri

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

Language: cpp

Time: 0.083 second

Submitted On: 2025-03-23 15:59:27

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

const int N = 401;
set<int> adj[N];
int train[N], car[N];
bool visited[N];
queue<int> q;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;
    memset(visited, false, sizeof(visited));
    memset(train, -1, sizeof(train));
    memset(car, -1, sizeof(car));
    train[1] = 0;
    car[1] = 0;

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

    q.push(1);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        if(visited[u]) continue;
        visited[u] = true;

        for(int v: adj[u]){
            if(train[v] == -1 or train[u] + 10*abs(v-u) < train[v]){
                train[v] = train[u] + 10*abs(v-u);
                q.push(v);
            }
        }
    }

    /*for(int i = 1; i <= n; i++) cout << train[i] << ' ';
    cout << '\n';*/

    memset(visited, false, sizeof(visited));

    q.push(1);

    while(!q.empty()){
        int u = q.front();
        q.pop();
        //cout << u << ' ';

        if(visited[u]) continue;
        visited[u] = true;

        for(int i = 1; i <= n; i++){
            if(u != i and adj[u].find(i) == adj[u].end()){
                if((car[i] == -1 or car[u] + 10*abs(i-u) < car[i]) and (train[i] != car[u] + 10*abs(i-u) or i == n)){
                    car[i] = car[u] + 10*abs(i-u);
                    //cout << i << ' ' << car[i] << ' ';
                    q.push(i);
                }
            }
        }
        //cout << '\n';
    }

    /*for(int i = 1; i <= n; i++) cout << car[i] << ' ';
    cout << '\n';*/

    if(car[n] == -1 or train[n] == -1) cout << -1;
    else{
        int temp = max(car[n], train[n]);
        cout << temp;
    }
}