Submission

Score: 100

User: kittipos

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

Language: cpp

Time: 0.022 second

Submitted On: 2026-03-05 12:42:18

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


int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> road;
    vector<vector<int>> train;
    road.assign(n, vector<int>(n, 0));
    train.assign(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            road[i][j] = 10 * abs(i - j);
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        road[a][b] = -1;
        road[b][a] = -1;
        train[a][b] = 10 * abs(a - b);
        train[b][a] = 10 * abs(a - b);
    }

    // calculate car time
    int best_car;
    {
        queue<int> q;
        q.push(0);
        vector<int> node_distance;
        node_distance.assign(n, numeric_limits<int>::max());
        node_distance[0] = 0;
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            for (int i = 0; i < n; i++) {
                if (i == current || road[current][i] == -1) {
                    continue;
                }

                if (road[current][i] + node_distance[current] < node_distance[i]) {
                    node_distance[i] = road[current][i] + node_distance[current];
                    q.push(i);
                }
            }
        }
        best_car = node_distance[n - 1];
    }

    int best_train;
    {
        queue<int> q;
        q.push(0);
        vector<int> node_distance;
        node_distance.assign(n, numeric_limits<int>::max());
        node_distance[0] = 0;
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            for (int i = 0; i < n; i++) {
                if (i == current || train[current][i] == -1) {
                    continue;
                }

                if (train[current][i] + node_distance[current] < node_distance[i]) {
                    node_distance[i] = train[current][i] + node_distance[current];
                    q.push(i);
                }
            }
        }
        best_train = node_distance[n - 1];
    }


    int res = max(best_car, best_train);
    if (res == 2147483647)
    {
        cout << -1 << endl;
    } else {
        cout << res << endl;
    }
    

    return 0;
}