Submission

[PPPPPPPPPPPPPPPPP-SS]

Score: 0

User: fluke

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

Language: cpp

Time: 0.022 second

Submitted On: 2025-03-14 20:29:58

#include <bits/stdc++.h>
#define ll long long 
#define f first 
#define s second 
#define pii pair<int,int>
#define piii tuple <int,int,int> 
#define emb emplace_back
#define em emplace 
#define all(x) x.begin(),x.end()
#define sp <<" "<<
#define DB cout<<"\n";system("pause");
using namespace std;

int inf = 2e9;
int mod = 1e9+7;

int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};

int main(){
ios::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector <vector <bool>> adj_m(n+1 , vector <bool> (n+1));
    vector <vector <int>> adj_t(n+1),adj_c(n+1);

    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        adj_m[x][y] = true;
        adj_m[y][x] = true;

        adj_t[x].emb(y);
        adj_t[y].emb(x);
    }

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(!adj_m[i][j]){
                adj_c[i].emb(j);
                adj_c[j].emb(i);
            }
        }
    }
    
    vector <int> dis_train(n+1,2e9) , dis_car(n+1,2e9);
    priority_queue <pii , vector <pii> , greater <pii>> pq;

    pq.em(0,1);
    while(!pq.empty()){
        auto [dis_now , node_now]  = pq.top();
        pq.pop();

        if(dis_now >= dis_train[node_now])continue;
        dis_train[node_now] = dis_now;

        for(auto x : adj_t[node_now]){
            if(dis_train[x] <= dis_now + 10 * abs(node_now - x))continue;
            pq.em(dis_now + 10 * abs(node_now - x) , x);
        }
    }

    pq.em(0,1);
    while(!pq.empty()){
        auto [dis_now , node_now]  = pq.top();
        pq.pop();

        if(dis_now >= dis_car[node_now])continue;
        dis_car[node_now] = dis_now;

        for(auto x : adj_c[node_now]){
            if(x == n){
                if(dis_car[x] <= dis_now + 10 * abs(node_now - x))continue;
                pq.em(dis_now + 10 * abs(node_now - x)  , x);
            }
            else {
                if(dis_car[x] <= dis_now + 10 * abs(node_now - x) || dis_train[x] == dis_now + 10 * abs(node_now - x))continue;
                pq.em(dis_now + 10 * abs(node_now - x) ,x);

            }
        }
    }

    int use = max(dis_train[n] , dis_car[n]);
    if(use == inf)cout<<"-1";
    else cout<<use;


}