Submission

[P-SSSSSSSSSSSSSSSSSS]

Score: 0

User: noname

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-30 15:40:45

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

int BFS(unordered_map<int, vector<pair<int, int>>>&g, int start, int end) {
    unordered_map<int, int> dist;
    queue<int> q;

    for(auto &[city, _] : g) {
        dist[city] = INT_MAX;
    }

    q.push(start);
    dist[start] = 0;

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

        for(auto &[neighbor, time] : g[currCity]) {
            int newTime = dist[currCity] + time;
            if(newTime < dist[neighbor]) {
                dist[neighbor] = newTime;
                q.push(neighbor);
            }
        }
    }

    return dist[end] == INT_MAX ? -1 : dist[end];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int des, ways;
    cin >> des >> ways;

    unordered_map<int, vector<pair<int, int>>> trainGraph;
    unordered_map<int, vector<pair<int, int>>> carGraph;
    for(int i = 0; i < ways; i++) {
        int x, y;
        cin >> x >> y;
        trainGraph[x].push_back({y, abs(y - x) * 10});
        trainGraph[y].push_back({x, abs(y - x) * 10});
    }

    for(int i = 1; i <= des; i++) {
        for(int j = i + 1; j <= des; j++) {
            bool hasTrainPath = false;
            for(auto pair : trainGraph[i]) {
                if(pair.first == j) {
                    hasTrainPath = true;
                    break;
                }
            }

            if(!hasTrainPath) {
                carGraph[i].push_back({j, abs(j - i) * 10});
                carGraph[j].push_back({i, abs(j - i) * 10});
            }
        }
    }

    //do bfs to find min time by abs(y -x) * 10
    //we can also travel by car(there is car path when there aren't train path)
    int startCity = 1;
    int minTimeByTrain = BFS(trainGraph, startCity, des);
    int minTimeByCar = BFS(carGraph, startCity, des);

    if(minTimeByTrain == -1 || minTimeByCar == -1) {
        cout << "-1" << endl;
        return 0;
    }

    cout << max(minTimeByCar, minTimeByTrain) << endl;

    return 0;
}