Submission

Score: 100

User: winniecoder1029

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

Language: cpp

Time: 0.032 second

Submitted On: 2026-03-05 21:44:38

#include <bits/stdc++.h>
using namespace std;
#define MAX numeric_limits<int>::max()

int dijkstra(int size, vector<vector<int>> am) {
    // do dijkstra from vertices 0 to vertices size-1
    // return -1 if no paths found, otherwise return the distance of the shortest path
    vector<int> dist(size, MAX);
    vector<bool> visited(size, false);

    dist[0] = 0;

    for (int i = 0; i < size; i++) {
        int u = -1;
        int minDist = MAX;

        // find unvisited node with smallest distance
        for (int j = 0; j < size; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }

        if (u == -1) break; // all visited
        visited[u] = true; 

        // relax neighbors
        for (int v = 0; v < size; v++) {
            if (am[u][v] != MAX && !visited[v]) { // if have a path and havent visited
                if (dist[u] + am[u][v] < dist[v]) { // 
                    dist[v] = dist[u] + am[u][v];
                }
            }
        }
    }

    if (dist[size - 1] == MAX) return -1;
    return dist[size - 1];
}

int main() {
    int n, m;
    cin >> n >> m;
    // weighted adjacency matrices of graph with n vertices
    vector<vector<int>> amTrain(n, vector<int>(n, MAX));
    vector<vector<int>> amCar(n, vector<int>(n, MAX));
    // precalculate amCar
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            amCar[i][j] = 10*abs(j-i);
        }
    }
    
    for (int i = 0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        amTrain[x-1][y-1] = 10*abs(x-y);
        amTrain[y-1][x-1] = 10*abs(x-y);
        amCar[x-1][y-1] = MAX;
        amCar[y-1][x-1] = MAX;
    }
    //debug
    /*
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if (amTrain[i][j] == MAX) cout << "m";
            else cout << amTrain[i][j];
            cout << "\t";
        }
        cout << endl;
    }
    cout << endl << endl;
    //debug 2
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if (amCar[i][j] == MAX) cout << "m";
            else cout << amCar[i][j];
            cout << "\t";
        }
        cout << endl;
    }
    // 
    */
    int trainDist = dijkstra(n, amTrain);
    if (trainDist == -1) {
        cout << -1;
        return 0;
    }
    int carDist = dijkstra(n, amCar);
    if (carDist == -1) {
        cout << -1;
        return 0;
    } else {
        cout << max(trainDist, carDist);
    }
    
}