４つに場合分けできる
・町１から町Nまで未定のテレポーターを使わないで行く。
・町１から近い未定のテレポーターまで行き、町iから未定のテレポーターを使わないで町Nまでいく。
・町１から町iまで行き、未定のテレポーターにテレポートした後、町Nまで行く
・町１から未定のテレポーターに行き、町iに行く。さらに町iから未定のテレポーターにテレポートし、町Nまで行く。
また、使う未定のテレポーターはそれぞれ町１、町Nから一番近いものを使用する。
双方向からBFSなどを行い、町１からそれぞれの町までの距離、町Nからそれぞれの町までの距離を配列に格納し、町１から一番近い未定のテレポーターまでの距離、町Nから一番近い未定のテレポーターまでの距離を変数などに格納し、この動作を高速に行う。
#include <bits/stdc++.h> using namespace std; vector<int> bfs(int n,vector<vector<int>>rotti,int start){ vector<int>stack{start},amount(n,1000000000); int iti=0,hako; amount[start-1]=0; while (stack.size()>iti){ hako=stack[iti]; for (int i=0;i<rotti[hako-1].size();i++){ if(amount[rotti[hako-1][i]-1]<=amount[hako-1]+1)continue; amount[rotti[hako-1][i]-1]=amount[hako-1]+1; stack.emplace_back(rotti[hako-1][i]); } iti++; } return amount; } int main() { int n,m,a,b; cin >> n >> m; vector<vector<int>>rotti(n); vector<int>x; for (int i=0;i<m;i++){ cin >> a >> b; if(a==0){ x.emplace_back(b); continue; } rotti[a-1].emplace_back(b); rotti[b-1].emplace_back(a); } vector<int>amount=bfs(n,rotti,1); vector<int>amount2=bfs(n,rotti,n); int count=100000000,count2=100000000; for (int i=0;i<x.size();i++)count=min(count,amount[x[i]-1]); for (int i=0;i<x.size();i++)count2=min(count2,amount2[x[i]-1]); for (int i=0;i<n;i++){ if (min({amount[n-1],count2+1+amount[i],count+1+amount2[i],count2+count+2})>=10000000)cout << -1 << " "; else cout << min({amount[n-1],count+1+amount2[i],count2+1+amount[i],count+2+count2}) << " "; } cout << endl; return 0; }
