Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: noname

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

Language: cpp

Time: 0.142 second

Submitted On: 2025-03-30 16:08:33

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

int bfs(unordered_map<int, vector<pair<int, int>>> &g, int start, int end) {
    if(g[start].empty()) return -1; //no way to go

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

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

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

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

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

int main() {
    int des, ways;
    cin >> des >> ways;

    unordered_map<int, vector<pair<int, int>>> tg;
    unordered_map<int, vector<pair<int, int>>> cg;
    unordered_set<string> trainPaths;
    for(int i = 0; i < ways; i++) {
        int x, y;
        cin >> x >> y;
        tg[x].push_back({y, abs(x - y) * 10});
        tg[y].push_back({x, abs(x - y) * 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 path = to_string(i) + "-" + to_string(j);
            if(trainPaths.find(path) == trainPaths.end()) {
                cg[i].push_back({j, abs(i - j) * 10});
                cg[j].push_back({i, abs(i - j) * 10});
            }
        }
    }

    int minTrain = bfs(tg, 1, des);
    int minCar = bfs(cg, 1, des);

    if(minTrain == -1 || minCar == -1) cout << "-1" << endl;
    else cout << max(minCar, minTrain) << endl;

    return 0;
}