Submission

Score: 100

User: 12345678

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

Language: cpp

Time: 0.069 second

Submitted On: 2025-11-09 10:24:30

#include <bits/stdc++.h>

using namespace std;

const int nx=405, inf=1e9;

int n, m, u, v, a[nx][nx], b[nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) a[i][j]=(i==j)?0:inf, b[i][j]=10*abs(i-j);
    for (int i=1; i<=m; i++)
    {
        cin>>u>>v;
        a[u][v]=a[v][u]=10*abs(u-v);
        b[u][v]=b[v][u]=inf;
    }
    for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) a[i][j]=min(a[i][j], a[i][k]+a[k][j]), b[i][j]=min(b[i][j], b[i][k]+b[k][j]);
    if (a[1][n]==inf||b[1][n]==inf) cout<<-1;
    else cout<<max(a[1][n], b[1][n]);
}