Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: yumiKuri

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

Language: cpp

Time: 0.053 second

Submitted On: 2025-03-31 21:55:53

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

const int N = 401;
bool visited[N];
set<int> train[N], car[N];
int t_train[N], t_car[N];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

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

    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b;
        train[a].insert(b);
        train[b].insert(a);
    }

    for(int i = 1; i < n; i++){
        for(int j = i+1; j <= n; j++){
            if(train[i].find(j) == train[i].end()){
                //cout << i << ' ' << j << '\n';
                car[i].insert(j);
                car[j].insert(i);
            }
        }
    }

    /*for(int i = 1; i <= n; i++){
        cout << i << ": ";
        for(int x: car[i]) cout << x << ' ';
        cout << '\n';
    }*/

    fill(t_train, t_train+N, INT_MAX);
    memset(visited, false, sizeof(visited));

    pq.push({0,1});
    t_train[1] = 0;

    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();

        for(int v: train[u]){
            int dist = 10*abs(v-u);
            if(t_train[v] > t_train[u] + dist and !visited[v]){
                visited[u] = true;
                t_train[v] = t_train[u] + dist;
                pq.push({t_train[v], v});
            }
        }

    }

    //cout << t_train[n] << '\n';

    fill(t_car, t_car+N, INT_MAX);
    memset(visited, false, sizeof(visited));
    t_car[1] = 0;

    pq.push({0,1});

    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        //cout << u << '\n';

        for(int v: car[u]){
            int dist = 10*abs(v-u);
            if(t_car[v] > t_car[u] + dist and !visited[v]){
                //cout << v << ": " << t_car[u] + dist << '\n';
                //if(t_train[v] != t_car[u] + dist or v == n){
                    t_car[v] = t_car[u] + dist;
                    visited[u] = true;
                    pq.push({t_car[v], v});
                //}
            }
        }
    }

    //cout << t_car[n] << '\n';

    if(t_car[n] == INT_MAX or t_train[n] == INT_MAX) cout << -1;
    else{
        int temp = max(t_car[n], t_train[n]);
        cout << temp;
    }
}