Submission

[-SSSSSSSSSSSSSSSSSSS]

Score: 0

User: nebura

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-31 23:10:13

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

struct Edge {
    int to, weight;
};

void dijkstra(int start, const vector<vector<Edge>> &graph, vector<int> &dist) {
    int n = graph.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;

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

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue;

        for (const Edge& e : graph[u]) {
            int v = e.to;
            int w = e.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<Edge>> trainGraph(N + 1);
    vector<vector<Edge>> carGraph(N + 1);

    // Input train rail connections (rural rail)
    for (int i = 0; i < M; ++i) {
        int U, V;
        cin >> U >> V;

        int weight = 10 * abs(V - U);
        trainGraph[U].push_back({V, weight});
        trainGraph[V].push_back({U, weight});
    }

    // Create car road graph (all pairwise cities not connected by train)
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            int weight = 10 * abs(j - i);
            if (trainGraph[i].empty()) {
                carGraph[i].push_back({j, weight});
                carGraph[j].push_back({i, weight});
            }
        }
    }

    // Run Dijkstra for both car and train
    vector<int> distTrain(N + 1), distCar(N + 1);
    dijkstra(1, trainGraph, distTrain);
    dijkstra(1, carGraph, distCar);

    // Get the minimum time to meet at city N
    int time = min(distTrain[N], distCar[N]);

    if (distTrain[N] == INT_MAX || distCar[N] == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << time << endl;
    }

    return 0;
}