Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Jibhong

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

Language: cpp

Time: 0.184 second

Submitted On: 2025-03-23 16:47:05

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> pii;
bool edge[405][405];
priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>pq;
vector<int> distA(405,2e9);
vector<int> distB(405,2e9);
bool visA[405];
bool visB[405];
int main(){
    int n,e;
    cin>>n>>e;
    for(int i=0;i<e;++i){
        int u,v;
        cin>>u>>v;
        edge[u][v]=1;
        edge[v][u]=1;
    }
    pq.push({0,{1,1}});
    distA[1]=0;
    distB[1]=0;
    while(!pq.empty()){
        int nowA=pq.top().S.F;
        int nowB=pq.top().S.S;
        pq.pop();
        if(nowA==nowB && nowA!=1)continue;
        for(int tonodeA=1;tonodeA<=n;++tonodeA){
            if(!edge[nowA][tonodeA] || tonodeA==nowA)continue;
            for(int tonodeB=1;tonodeB<=n;++tonodeB){
                if(edge[nowB][tonodeB] || tonodeB==nowB)continue;
                if(tonodeA==tonodeB)continue;
                int maxold=max(distA[tonodeA],distB[tonodeB]);
                int maxnew=max(distA[nowA]+abs(nowA-tonodeA),distB[nowB]+abs(nowB-tonodeB));
                if(maxold<=maxnew)continue;
                distA[tonodeA]=distA[nowA]+abs(nowA-tonodeA);
                distB[tonodeB]=distB[nowB]+abs(nowB-tonodeB);
                pq.push({maxnew,{tonodeA,tonodeB}});
            }
        }
    }
    int out=max(distA[n],distB[n]);
    if(out==2e9)
        cout<<-1;
    else
        cout<<out*10;
    return 0;
}