Submission

Score: 100

User: osensunny

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

Language: cpp

Time: 0.013 second

Submitted On: 2025-03-21 20:37:43

#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>

void dijkstra(vvii &adj, vi &time, vi &dist, vi &nx, int src, int V){
    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});
                nx[u] = v;
            }
        }
    }

    int x = 1, cnt = 1;
    while(x != -1){
        time[x] = cnt;
        x = nx[x];
        cnt++;
    }
}

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

    int V, E, a, b;
    cin >> V >> E;

    vi distTrain(V+1, 1e9), distCar(V+1, 1e9), timeTrain(V+1, 0), timeCar(V+1, 0), nxTrain(V+1, -1), nxCar(V+1, -1);
    vvii adjTrain(V+1), adjCar(V+1);
    vvb checkTrain(V+1, vb(V+1, false));

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

    dijkstra(adjTrain, timeTrain, distTrain, nxTrain, 1, V);
    dijkstra(adjCar, timeCar, distCar, nxCar, 1, V);

    if(distTrain[V] == 1e9 || distCar[V] == 1e9){
        cout << -1;
        return 0;
    }

    int node = nxTrain[1];
    while(node != -1){
        if(timeTrain[node] == timeCar[node]){
            cout << -1;
            return 0;
        }
        node = nxTrain[node];
    }

    cout << max(distTrain[V], distCar[V]);

    return 0;
}