Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Nakornrat

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

Language: cpp

Time: 0.019 second

Submitted On: 2025-03-22 21:58:08

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int cnt = 0;
using pii = pair<int, int>;
int n, m;
vector<vector<pii>> ght;
vector<vector<pii>> ghc;
bool mem[4010][4010];
int dijkstra(vector<vector<pii>> &gh, vector<int> &dist){
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, 1});
    dist[1] = 0;
    while(!q.empty()){
        auto [uw, un] = q.top();q.pop();
        if(uw>dist[un])continue;
        for(auto [vn, vw]:gh[un]){
            int ww = dist[un] + vw;
            if(ww<dist[vn]){
                dist[vn] = ww;
                q.push({ww, vn});
            }
        }
    }
    if(dist[n]==INT_MAX)return -1;
    return dist[n];
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    vector<int> distt(n+1, INT_MAX);
    vector<int> distc(n+1, INT_MAX);
    ght.resize(n+1);
    ghc.resize(n+1);
    while(m--){
        int u, v;cin>>u>>v;
        int weight = 10*(v-u);
        if(weight<0)weight = -weight;
        ght[u].push_back({v, weight});
        ght[v].push_back({u, weight});
        mem[u][v] = mem[v][u] = 1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mem[i][j]||i==j)continue;
            mem[i][j] = mem[j][i] = 1;
            int weight = 10*(j-i);
            if(weight<0)weight = -weight;
            ghc[i].push_back({j, weight});
            ghc[j].push_back({i, weight});
        }
    }
    int train = dijkstra(ght, distt);
    int car = dijkstra(ghc, distc);
    if(train==-1||car==-1)cout<<-1;
    else cout<<max(train, car);

}