Submission

[P-SSSSSSSSSSSSSSSSSS]

Score: 0

User: AungS8430

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-16 12:07:45

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <tuple>
#include <set>

using namespace std;

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

    vector<vector<pair<int, int>>> train_adj(n + 1);
    vector<vector<pair<int, int>>> car_adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        int weight = 10 * abs(u - v);
        train_adj[u].push_back({v, weight});
        train_adj[v].push_back({u, weight});
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j) {
                int weight = 10 * abs(i - j);
                car_adj[i].push_back({j, weight});
            }
        }
    }

    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> pq;
    pq.push({0, 0, 1, 1});

    set<tuple<int, int, int, int>> visited;

    int min_time = -1;

    while (!pq.empty()) {
        int car_time, train_time, car_city, train_city;
        tie(car_time, train_time, car_city, train_city) = pq.top();
        pq.pop();

        if (car_city == n && train_city == n) {
            min_time = max(car_time, train_time);
            break;
        }

        if (visited.count({car_city, train_city, car_time, train_time})) {
            continue;
        }
        visited.insert({car_city, train_city, car_time, train_time});

        for (auto& car_next : car_adj[car_city]) {
            int next_car_city = car_next.first;
            int next_car_time = car_time + car_next.second;

            for (auto& train_next : train_adj[train_city]) {
                int next_train_city = train_next.first;
                int next_train_time = train_time + train_next.second;

                if ((next_car_city != next_train_city || (next_car_city == n && next_train_city == n))) {
                    pq.push({next_car_time, next_train_time, next_car_city, next_train_city});
                }
            }
        }
    }

    cout << min_time << endl;

    return 0;
}