Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: osensunny

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

Language: cpp

Time: 0.015 second

Submitted On: 2025-03-21 20:51:04

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

#define ii pair<int, int>
#define fi first
#define se second
#define vii vector<ii>
#define vvii vector<vii>
#define vi vector<int>
#define vb vector<bool>
#define vvb vector<vb>

int V, E, a, b;
vvb checkTrain(405, vb(405));

int dijkstra(vvii &adj, int src){
    vi dist(V+1, 1e9);
    vb vis(V+1, false);
    dist[src] = 0;
    priority_queue<ii, vii, greater<ii>> pq;
    pq.push({dist[src], src});

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

        int u = fr.se;
        if(vis[u]) continue;
        vis[u] = true;

        for(auto edge: adj[u]){
            int w = edge.fi, v = edge.se;
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist[V];
}

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

    vvii adjTrain(405), adjCar(405);
    cin >> V >> E;
    for(int i=0; i<E; i++){
        cin >> a >> b;
        adjTrain[a].push_back({abs(a-b)*10, b});
        adjTrain[b].push_back({abs(a-b)*10, a});
        checkTrain[a][b] = true;
        checkTrain[b][a] = true;
    }

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

    int distTrain = dijkstra(adjTrain, 1);
    int distCar = dijkstra(adjCar, 1);

    if(distTrain == 1e9 || distCar == 1e9) cout << -1;
    else cout << max(distTrain, distCar);

    return 0;
}