Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: noname

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

Language: cpp

Time: 0.085 second

Submitted On: 2025-03-30 15:50:21

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

int BFS(unordered_map<int, vector<pair<int, int>>>& g, int start, int end) {
    if (g.find(start) == g.end()) return -1;

    unordered_map<int, int> dist;
    queue<pair<int, int>> q;

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

    while (!q.empty()) {
        auto [currCity, currTime] = q.front();
        q.pop();

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

    return dist.count(end) ? dist[end] : -1;
}

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;
    unordered_set<string> trainPaths;

    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});
        trainPaths.insert(to_string(x) + "-" + to_string(y));
        trainPaths.insert(to_string(y) + "-" + to_string(x));
    }

    for (int i = 1; i <= des; i++) {
        for (int j = i + 1; j <= des; j++) {
            string pathKey = to_string(i) + "-" + to_string(j);
            if (trainPaths.find(pathKey) == trainPaths.end()) {
                carGraph[i].push_back({j, abs(j - i) * 10});
                carGraph[j].push_back({i, abs(j - i) * 10});
            }
        }
    }

    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;
}