Submission

[PPP-SSSSSSSSSSSSSSSS]

Score: 0

User: FotoFatTurtle

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-20 13:29:39

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int node,edge,te,mp;
    cin>>node>>edge;
    vector<vector<int>> adj(node+1);
    bool run[node+1][node+1]={};
    bool train=false;
    for(int i=0;i<edge;i++)
    {
        cin>>te>>mp;
        adj[te].push_back(mp);
        adj[mp].push_back(te);
        run[te][mp]=true;
        run[mp][te]=true;
        if((te==1&&mp==node)||(mp==1&&te==node))
        {
            train=true;
        }
    }
    int anst,ansc,temp;
    int dist[node+1];
    for(int i=1;i<=node;i++)
        dist[i]=2e9;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    if(train==true)
    {
        anst=10*(node-1);
        vector<vector<int>> adjcar(node+1);
        for(int i=1;i<=node;i++)
        {
            for(int j=1;j<=node;j++)
            {
                if(run[i][j]==false)
                {
                    adjcar[i].push_back(j);
                }
            }
        }
        dist[1]=0;
        q.push({0,1});
        while(!q.empty())
        {
            te=q.top().f;
            mp=q.top().s;
            q.pop();
            if(dist[mp]<te)
                continue;
            for(int i=0;i<adjcar[mp].size();i++)
            {
                temp=adjcar[mp][i]-mp;
                if(temp<0)
                    temp*=-1;
                if(dist[adjcar[mp][i]]>te+10*temp)
                {
                    dist[adjcar[mp][i]]=te+10*temp;
                    q.push({te+10*temp,adjcar[mp][i]});
                }
            }
        }
        ansc=dist[node];
        if(dist[node]==2e9)
        {
            cout<<"-1";
        }
        else
            cout<<max(anst,ansc);
    }
    else
    {
        ansc=10*(node-1);
        dist[1]=0;
        q.push({0,1});
        while(!q.empty())
        {
            te=q.top().f;
            mp=q.top().s;
            q.pop();
            if(dist[mp]<te)
                continue;
            for(int i=0;i<adj[mp].size();i++)
            {
                temp=adj[mp][i]-mp;
                if(temp<0)
                    temp*=-1;
                if(dist[adj[mp][i]]>te+10*temp)
                {
                    dist[adj[mp][i]]=te+10*temp;
                    q.push({te+10*temp,adj[mp][i]});
                }
            }
        }
        anst=dist[node];
        if(dist[node]==-1)
        {
            cout<<"-1";
        }
        else
            cout<<max(ansc,anst);
    }
}