Submission

Score: 100

User: erng

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

Language: cpp

Time: 0.013 second

Submitted On: 2025-12-30 22:15:29

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

#define ll long long

const ll nx=405;

ll n, m, x, y, mp[nx][nx], vs1[nx], vs2[nx], mn1[nx], mn2[nx];
vector<ll> adj1[nx], adj2[nx];
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> q;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=0; i<m; i++)
    {
        cin>>x>>y;
        adj1[x].push_back(y);
        adj1[y].push_back(x);
        mp[x][y]=1;
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (!mp[i][j] && i!=j && !mp[j][i])
            {
                adj2[i].push_back(j);
            }
        }
    }
    q.push({0, 1});
    for (int i=2; i<=n; i++)
    {
        mn1[i]=4e18;
        mn2[i]=4e18;
    }
    while(!q.empty())
    {
        auto [u, v]=q.top();
        q.pop();
        if (vs1[v]) continue;
        vs1[v]=1;
        for (int i=0; i<adj1[v].size(); i++)
        {
            auto cu=adj1[v][i];
            if (mn1[cu]>mn1[v]+(abs(v-cu))*10)
            {
                mn1[cu]=mn1[v]+(abs(v-cu))*10;
                q.push({mn1[cu], cu});
            }
        }
    }
    q.push({0, 1});
    while(!q.empty())
    {
        auto [u, v]=q.top();
        q.pop();
        if (vs2[v]) continue;
        vs2[v]=1;
        for (int i=0; i<adj2[v].size(); i++)
        {
            auto cu=adj2[v][i];
            if (mn2[cu]>mn2[v]+(abs(v-cu))*10)
            {
                mn2[cu]=mn2[v]+(abs(v-cu))*10;
                q.push({mn2[cu], cu});
            }
        }
    }

    if (!vs1[n] || !vs2[n])
    {
        cout<<-1;
        return 0;
    }
    cout<<max(mn1[n], mn2[n]);
}