Submission

Score: 100

User: NovemNotes

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

Language: cpp

Time: 0.014 second

Submitted On: 2026-03-11 11:45:45

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

#define int long long
const int inf = 1000000000000000009;
const int N = 409;

struct stc{
    int en,w;
    bool operator <(const stc &x)const{
        return w > x.w;
    }
};

int n,m;
bool mark[N][N];
int d1[N],d2[N];
vector<pair<int,int>> adj1[N],adj2[N];

void solve1(){
    priority_queue<stc> pq;
    pq.push({1,0});
    d1[1]=0;
    while(!pq.empty()){
        auto [en,w] = pq.top();pq.pop();
        if(w>d1[en])continue;
        for(auto [to,we]:adj1[en]){
            if(w+we<d1[to]){
                d1[to]=w+we;
                pq.push({to,w+we});
            }
        }
    }
}

void solve2(){
    priority_queue<stc> pq;
    pq.push({1,0});
    d2[1]=0;
    while(!pq.empty()){
        auto [en,w] = pq.top();pq.pop();
        if(w>d2[en])continue;
        for(auto [to,we]:adj2[en]){
            if(w+we<d2[to]){
                d2[to] = w+we;
                pq.push({to,w+we});
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++)d1[i]=d2[i]=inf;
    for(int i=0;i<m;i++){
        int a,b;cin >> a >> b;
        mark[a][b]=mark[b][a]=true;
        adj1[a].emplace_back(b,10*abs(a-b));
        adj1[b].emplace_back(a,10*abs(a-b));
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(!mark[i][j]){
                adj2[i].emplace_back(j,10*abs(i-j));
                adj2[j].emplace_back(i,10*abs(i-j));
            }
        }
    }
    solve1();
    solve2();
    if(d1[n]==inf || d2[n]==inf)cout << "-1\n";
    else{
        cout << max(d1[n],d2[n]) << "\n";
    }
    return 0;
}