高橋くんと不思議な道

C - 高橋くんと不思議な道

配列dを0からの最短距離とする
dをINFで初期化してd[0]を0にする

while(true){
Aの道でdを更新出来る場所を全部更新する
現在のdからBの道1回で更新できるdを全部更新する（この時のBによるコストはwhileループが何回目かを見ればいい）
更新が起きなかったらbreak;
}

Bの回数が小さい順に更新して行くことでd自体を貪欲に更新して行けるのが嬉しい
計算量は分からん

実装ではBの道を見てからAの道を見てるけど最初に0からBの道見る前にAの道見てあげるように調整必要

#include <bits/stdc++.h>
using namespace std;

#define int long long
const long long LINF=1e18;

signed main(){
  int n,m,cnt=-2;cin>>n>>m;
  vector<int> aed[n],bed[n],ans(n,LINF);
  while(m--){
    int c,u,v;cin>>c>>u>>v;
    (c?bed:aed)[u].push_back(v);
    (c?bed:aed)[v].push_back(u);
  }
  ans[0]=0;
  queue<int> que;
  que.push(0);
  while(true){
    map<int,int> mp;
    if(++cnt>=0)
      for(int i=0;i<n;i++)
        if(ans[i]<LINF)
          for(int p:bed[i])
            if(ans[p]>ans[i]+1+cnt&&(!mp[p]||mp[p]>ans[i]+1+cnt))
              mp[p]=ans[i]+1+cnt;
    if(cnt>=0&&mp.size()==0)break;

    for(auto p:mp){
      ans[p.first]=p.second;
      que.push(p.first);
    }

    while(que.size()){
      int p=que.front();que.pop();
      for(int q:aed[p])
        if(ans[q]>ans[p]+1){
          ans[q]=ans[p]+1;
          que.push(q);
        }
    }
  }
  for(int i=0;i<n;i++)cout<<ans[i]<<endl;
}

Submission #11897657 - AtCoder Regular Contest 052