Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Nightingale

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

Language: cpp

Time: 0.061 second

Submitted On: 2025-03-31 16:30:44

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int,vector<int>> path1;
map<int,vector<int>> path2;

void star(vector<int> &meta1){
  queue<int> here;
  here.push(1);
  while(here.empty()==0){
    int start = here.front();
    here.pop();
    for(auto it=path1[start].begin();it!=path1[start].end();it++){
      if(meta1[start]+abs(*it-start)*10<meta1[*it]){
        meta1[*it] = meta1[start]+abs(*it-start)*10;
        here.push(*it);
      }
    }
  }
}
void star2(vector<int> &meta2){
  queue<int> here;
  here.push(1);
  while(here.empty()==0){
    int start = here.front();
    here.pop();
    for(auto it=path2[start].begin();it!=path2[start].end();it++){
      if(meta2[start]+abs(*it-start)*10<meta2[*it]){
        meta2[*it] = meta2[start]+abs(*it-start)*10;
        here.push(*it);
      }
    }
  }
}
int32_t main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int a,b;
  cin >> a >> b;
  vector<int> meta1(a+1,LLONG_MAX);
  vector<int> meta2(a+1,LLONG_MAX);
  meta1[1] = 0;
  meta2[1] = 0;
  vector<int> visited1(a+1,0);
  vector<int> visited2(a+1,0);
  for(int i=1;i<=b;i++){
    int c,d;
    cin >> c >> d;
    path1[c].push_back(d);
    path1[d].push_back(c);
  }
  for(int i=1;i<=a;i++){
    for(int j=1;j<=a;j++){
      if(i!=j&&count(path1[i].begin(),path1[i].end(),j)==0){
        path2[i].push_back(j);
      }
    }
  }
  star(meta1);
  star2(meta2);
  int ans = max(meta1[a],meta2[a]);
  if(ans==LLONG_MAX) cout << -1;
  else cout << ans;
}