Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: FotoFatTurtle

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

Language: cpp

Time: 0.017 second

Submitted On: 2025-03-20 13:57:52

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int node,edge,te,mp,temp;
int dij(vector<vector<pair<int,int>>> adj,int dist[])
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    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++)
        {
            if(dist[adj[mp][i].s]>adj[mp][i].f+te)
            {
                dist[adj[mp][i].s]=te+adj[mp][i].f;
                q.push({adj[mp][i].f+te,adj[mp][i].s});
            }
        }
    }
    //cout<<dist[node]<<"\n";
    return dist[node];
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>node>>edge;
    vector<vector<pair<int,int>>> adjt(node+1),adjc(node+1);
    bool run[node+1][node+1]={};
    bool train=false;
    for(int i=0;i<edge;i++)
    {
        cin>>te>>mp;
        temp=mp-te;
        if(temp<0)
            temp*=-1;
        adjt[te].push_back({10*temp,mp});
        adjt[mp].push_back({10*temp,te});
        run[te][mp]=true;
        run[mp][te]=true;
    }
    for(int i=1;i<=node;i++)
    {
        for(int j=1;j<=node;j++)
        {
            if(i!=j&&run[i][j]==false)
            {
                temp=j-i;
                if(temp<0)
                    temp*=-1;
                adjc[i].push_back({10*temp,j});
                //cout<<i<<" "<<j<<"\n";
            }
        }
    }
    int dist1[node+1],dist2[node+1];
    for(int i=1;i<=node;i++)
    {
        dist1[i]=2e9;
        dist2[i]=2e9;
    }
    int ansc,anst,ans;
    anst=dij(adjt,dist1);
    ansc=dij(adjc,dist2);
    ans=max(anst,ansc);
    if(anst==2e9||ansc==2e9)
    {
        ans=-1;
    }
    //cout<<anst<<" "<<ansc;
    cout<<ans;
}