Submission

Score: 100

User: Gump2011

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

Language: cpp

Time: 0.012 second

Submitted On: 2026-03-08 14:56:45

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long weight;
};

struct Node {
    int u;
    long long dist;
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

long long dijkstra(int n, int start, const vector<vector<Edge>>& adj) {
    vector<long long> dist(n + 1, INF);
    priority_queue<Node, vector<Node>, greater<Node>> pq;

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

    while (!pq.empty()) {
        Node top = pq.top();
        pq.pop();

        int u = top.u;
        long long d = top.dist;

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.push({edge.to, dist[edge.to]});
            }
        }
    }
    return dist[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<bool>> has_rail(n + 1, vector<bool>(n + 1, false));
    vector<vector<Edge>> adj_train(n + 1);
    vector<vector<Edge>> adj_car(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        has_rail[u][v] = has_rail[v][u] = true;
        long long travel_time = 10LL * abs(u - v);
        adj_train[u].push_back({v, travel_time});
        adj_train[v].push_back({u, travel_time});
    }

    // สร้างถนนสำหรับรถยนต์ (ส่วนที่ไม่มีรางรถไฟ)
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (!has_rail[i][j]) {
                long long travel_time = 10LL * abs(i - j);
                adj_car[i].push_back({j, travel_time});
                adj_car[j].push_back({i, travel_time});
            }
        }
    }

    long long train_time = dijkstra(n, 1, adj_train);
    long long car_time = dijkstra(n, 1, adj_car);

    if (train_time == INF || car_time == INF) {
        cout << -1 << endl;
    } else {
        cout << max(train_time, car_time) << endl;
    }

    return 0;
}