Submission

[PPPPPPPPPPPP-SSSSSSS]

Score: 0

User: dwad2

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

Language: cpp

Time: 0.004 second

Submitted On: 2025-03-20 21:59:39

#include <bits/stdc++.h>

#define vi vector<int>

using namespace std;

void addver(vector<vi> &graph, int a, int b) {
    graph[a].push_back(b);
}

int dijkstra(vector<vi> &graph, int s) {

    int n = graph.size();

    priority_queue<int, vi, greater<int>> pq;
    vector<bool> check(n, false);
    vi dist(n, INT_MAX);
    dist[s] = 0;
    pq.push(s);
    check[s] = true;

    while(!pq.empty()) {
        int u = pq.top();
        pq.pop();
        for(int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            dist[v] = min(dist[v], dist[u] + 10 * abs(u - v));
            if(check[v] == false) {
                pq.push(v);
                check[v] = true;
            }
        }
    }
    if(dist[n - 1] == INT_MAX) return -1;
    else return dist[n - 1];

}

int main() {

    int ncity, ntrain;
    cin >> ncity >> ntrain;

    vector<vi> graph(ncity + 1);
    vector<vi> graph2(ncity + 1);

    int a, b;
    for(int i = 0; i < ntrain; i++) {
        cin >> a >> b;
        addver(graph, a, b);
        addver(graph, b, a);
    }

    bool check;
    for(int i = 1; i < ncity + 1; i++) {
        for(int j = 1; j < ncity + 1; j++) {
            for(int k = 0; k < graph[i].size(); k++) {
                if(graph[i][k] == j) {
                    check = false;
                    break;
                }
                check = true;
            }
            if(check == true) {
                graph2[i].push_back(j);
            }
        }
    }

// for(int i = 1; i < graph2.size(); i++) {
//     cout << i << " : ";
//     for(int j = 0; j < graph[i].size(); j++) {
//         cout << graph2[i][j] << " ";
//     }
//     cout << endl;
// }

// cout << dijkstra(graph, 1);
// cout << endl;
// cout << dijkstra(graph2, 1);
    if(dijkstra(graph, 1) == -1 || dijkstra(graph2, 1) == -1) cout << -1;
    else cout << max(dijkstra(graph, 1), dijkstra(graph2, 1));

    return 0;
}