ARC061 E すぬけ君の地下鉄旅行 01BFSに帰着

ARC061 E すぬけ君の地下鉄旅行

問題概要

リンク参照

考察

  • 見た感じ最短経路問題
  • ただし,単純な最短経路問題ではなく,会社の情報が必要.これは,乗り換え時にコストがかかるため
  • 同じ会社の地下鉄を使う場合:コストがかからないのでコスト0の辺を張る
  • 違う会社の地下鉄に乗り換える場合:コスト1がかかる.この時点でコスト0または1の辺のみを張ればいいので01BFSが見えてくる.(頂点,会社)を持つので拡張01BFS的な名前でもつくのかしら?
  • 乗り換える際は,コスト0の辺を頂点-1(仮の頂点,改札を出るイメージ)に張り,頂点-1からコスト1の辺を改札を出た頂点に張ればよい(賢すぎでは,これ思いつくの)
  • こういうの解けるようになりたいね

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<queue>
#include<set>
#include<iomanip>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> P;
typedef long long int ll;
typedef pair<ll,ll> LLP;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define INF 1000000007
#define MOD 1000000007
#define ARRAY_MAX 100005



typedef struct edge{
    pair<int,int> to;//今いる位置、会社
    int cost;//移動にかかるコスト
}EDGE;

int n,m;
map<P,vector<EDGE> > G;
set<P> used;

int bfs(){

    deque<EDGE> deq;
    deq.push_back(EDGE{P(0,-1),0});
    int ans = -1;

    while(!deq.empty()){
        EDGE es = deq.front();
        deq.pop_front();
        if(used.find(es.to) != used.end()){
            //もう使ったので調べない
            continue;
        }
        used.insert(es.to);
        if(es.to == P(n-1,-1)){
            //目的地に着いた
            //つまり、駅nの改札を出たところなら
            ans = es.cost;
            break;
        }
        for(auto itr:G[es.to]){
            //次の駅の候補を調べる
            if(used.find(itr.to) != used.end()){
                //次の駅がすでに調べられているなら調べない
                continue;
            }
            if(itr.cost == 0){
                deq.push_front({itr.to,es.cost});
            }else{
                deq.push_back({itr.to,es.cost+1});
            }
        }       
    }
    return ans;
}



int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    cin >> n >> m;
    REP(i,m){
        int p,q,c;
        cin >> p >> q >> c;
        p--;
        q--;
        //同じ会社の間にコスト0の辺を張る
        G[P(p,c)].push_back((EDGE){P(q,c),0});
        G[P(q,c)].push_back((EDGE){P(p,c),0});


        //駅番号-1は駅から改札を出ることを表す,コスト0の辺を張る
        G[P(p,c)].push_back((EDGE){P(p,-1),0});
        G[P(q,c)].push_back((EDGE){P(q,-1),0});

        
        //改札を出て別の会社の駅に入る時にコスト1かかるとする,コスト1の辺を張る
        //途中で別の会社を使って再びもとの会社を使う時にもコストはかかる
        G[P(p,-1)].push_back((EDGE){P(q,c),1});
        G[P(q,-1)].push_back((EDGE){P(p,c),1});
    }

    int ans = bfs();
    cout << ans << endl;

    return 0;
}