Submission

[P-SSSSSSSSSSSSSSSSSS]

Score: 0

User: nebura

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-31 23:04: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 = 5;
    int M = 3;

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

    vector<pair<int, int>> temp = {{1, 3}, {3, 4}, {4, 5}};

    for (int i = 0; i < M; i++) {

        int u = temp[i].first;
        int v = temp[i].second;

        int weight = 10 * abs(u - v);

        trainGraph[u].push_back({v, weight});
        trainGraph[v].push_back({u, weight});
    }

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

    vector<int> distTrain(N + 1), distCar(N + 1);
    dijkstra(1, trainGraph, distTrain);
    dijkstra(1, carGraph, distCar);

    int time = min(distTrain[N], distCar[N]);

    if (time == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << time << endl;
    }
}