Submission

[PPPPPPPPPPPPPPPPP-SS]

Score: 0

User: hmmm

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

Language: cpp

Time: 0.014 second

Submitted On: 2025-03-15 17:26:19

#include<bits/stdc++.h>
using namespace std;
using pii=array<int,2>;
const int N=405;
int a[N][N],dis[N],dis2[N],ti[N],ti2[N],pa[N],pa2[N];
vector<pii> g[N],t[N];
bool vis[N],vis2[N];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back({v,10*abs(u-v)});
        g[v].push_back({u,10*abs(u-v)});
        int x=min(u,v);
        int y=max(u,v);
        a[x][y]=true;
    }
    for(int i=1;i<=n;i++){
        dis[i]=dis2[i]=1e9;
        for(int j=i+1;j<=n;j++){
            if(a[i][j]==false){
                t[i].push_back({j,10*abs(i-j)});
                t[j].push_back({i,10*abs(i-j)});
                // cout << i << ' ' << j << "aa\n";
            }
        }
    }
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push({dis[1]=0,1});
    while(!q.empty()){
        auto l=q.top()[0];
        auto x=q.top()[1];
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(auto e:g[x]){
            auto xx=e[0];
            auto ll=e[1];
            if(vis[xx]==false && dis[xx]>dis[x]+ll){
                dis[xx]=dis[x]+ll;
                q.push({dis[xx],xx});
                pa[x]=xx;
            }
        }
    }
    if(dis[n]==1e9){
        cout << "-1";
        return 0;
    }
    int to=1,cnt=1;
    while(to!=0){
        ti[to]=cnt++;
        to=pa[to];
    }
    q.push({dis2[1]=0,1});
    while(!q.empty()){
        auto l=q.top()[0];
        auto x=q.top()[1];
        q.pop();
        // cout << l << ' ' << x << "--\n";
        if(vis2[x]) continue;
        vis2[x]=true;
        for(auto e:t[x]){
            auto xx=e[0];
            auto ll=e[1];
            if(xx!=n) if(dis[xx]==dis2[x]+ll) continue;
            if(vis2[xx]==false && dis2[xx]>dis2[x]+ll){
                dis2[xx]=dis2[x]+ll;
                q.push({dis2[xx],xx});
                pa2[x]=xx;
            }
        }
    }
    if(dis2[n]==1e9){
        cout << "-1";
        return 0;
    }
    to=1,cnt=1;
    while(to!=0){
        if(ti[to]==cnt && 1<to && to<n){
            cout << "-1";
            return 0;
        }
        to=pa2[to];
        cnt++;
    }    
    cout << max(dis[n],dis2[n]);
    // for(int i=1;i<=n;i++){
    //     cout << dis[i] << ' ' << dis2[i] << "\n";
    // }
}