Submission

Score: 0

User: Jokul

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-19 18:16:35

#include<bits/stdc++.h>
#define ll long long
#define p pair<ll,ll>
using namespace std;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<vector<p>> adj(n),adj2(n);
    vector<vector<int>> count(n,vector<int>(n,0));
    vector<ll> dist1(n,INT_MAX),dist2(n,INT_MAX);
    dist1[0]=0;
    dist2[0]=0;
    for(int i=0;i<m;i++)
    {
        ll u,v;
        cin>>u>>v;
        adj[u-1].push_back({v-1,abs(u-v)});
        count[u-1][v-1]=1;
        adj[v-1].push_back({u-1,abs(u-v)});
        count[v-1][u-1]=1;
    }
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(count[i][j]==0)
            {
                adj2[i].push_back({j,abs(i-j)});
                adj2[j].push_back({i,abs(i-j)});
            }
        }
    }
    priority_queue<p,vector<p>,greater<p>> pq1;
    priority_queue<p,vector<p>,greater<p>> pq2;
    pq1.push({dist1[0],0});
    while(!pq1.empty())
    {
        auto[dis,loc]=pq1.top();
        pq1.pop();
        for(auto[pos,wage]:adj[loc])
        {
            if(dist1[pos]<=wage+dis)
            {
                continue;
            }
            dist1[pos]=wage+dis;
            pq1.push({dist1[pos],pos});
        }
    }
    pq2.push({dist2[0],0});
    while(!pq2.empty())
    {
        auto[dis,loc]=pq2.top();
        pq2.pop();
        for(auto[pos,wage]:adj2[loc])
        {
            if(dist2[pos]<=wage+dis)
            {
                continue;
            }
            dist2[pos]=wage+dis;
            pq2.push({dist2[pos],pos});
        }
    }
    if(dist2[n-1]==INT_MAX)
    {
        cout<<-1;
        return 0;
    }
    cout<<min(dist1[n-1],dist2[n-1])*10<<" ";
}