問題概要

駅$ 1 $から駅$ N $までの$ N $個の駅に対し，$ M $個の路線が存在する． $ i $番目の路線は駅$ p_i $と駅$ q_i $を相互に結び，会社$ c_i $によって運営されている．駅$ 1 $を出発地，駅$ N $を目的地とするとき，異なる会社の路線への最小の乗り換え回数を求める．

解法概要

f:id:noimin:20180419214944j:plain

各駅各会社に対応するノードを作ることで，最短経路問題に落とし込むことができる．例えば上の図は入力例1

に対応するグラフである．グラフの作り方は以下の通り．

ノード
- 各駅に対して，会社別のノードを用意する．はじめ会社の数はわからないので，路線の数だけ会社があると考えておく．($ 1 \leq c_i \leq M$とは限らないので，実装時は注意．私は$ c_i $の値について，出現した順に1から番号を振っていく実装にした)
- 乗り換えの際に経由するノード (図中のノード0,4,8のこと．以下乗り換え経由ノードとする)を用意する．もしこのノードを用意しないと，会社別のノードだけでは乗り換えを管理する際にO(会社数²)の本数のエッジを張らなければならなくなる．
エッジ
- 各入力行 (2行目以降) について，駅$ p_i $と駅$ q_i $の会社$ c_i $に対応するノード同士で両方向にコスト0のエッジを張る．
- 各駅各会社のノードについて，その駅の乗り換え経由ノードに向かってコスト0のエッジを張る．
- ↑とは逆方向にコスト1のエッジを張る．

あとはダイクストラ法などで駅1の乗り換えノードから駅Nの乗り換えノードまでの最小コストを求めればよい．

ソースコード

#include<iostream>
#include<queue>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;

map<ll, ll> d;
priority_queue< Pll, vector<Pll>, greater<Pll> > que;
map<ll, vector<Pll> > edges;
ll n,m,p,r,c;

void dijkstra(ll start){
    d[start] = 0LL;
    que.push(Pll(0LL, start));

    while(!que.empty()){
        Pll v = que.top(); que.pop();
        if(d.find(v.second) != d.end() && d[v.second] < v.first) continue;
        for(Pll e: edges[v.second]){
            if(d.find(e.first) == d.end() || d[e.first] > d[v.second] + e.second){
                d[e.first] = d[v.second] + e.second;
                que.push(Pll(d[e.first], e.first));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    map<ll, ll> lines;
    ll next_line = 1;
    for(int i=0;i<m;++i){
        cin >> p >> r >> c;
        p--; r--;
        if(lines[c] == 0) lines[c] = next_line++;
        c = lines[c];
        edges[p*(m+1LL)+c].emplace_back(r*(m+1LL)+c, 0LL);
        edges[r*(m+1LL)+c].emplace_back(p*(m+1LL)+c, 0LL);
        edges[p*(m+1LL)].emplace_back(p*(m+1LL)+c, 0LL);
        edges[p*(m+1LL)+c].emplace_back(p*(m+1LL), 1LL);
        edges[r*(m+1LL)].emplace_back(r*(m+1LL)+c, 0LL);
        edges[r*(m+1LL)+c].emplace_back(r*(m+1LL), 1LL);
    }

    dijkstra(0LL);
    if(d.find((n-1LL)*(m+1LL)) == d.end()){
        cout << -1 << endl;
    }else{
        cout << d[(n-1LL)*(m+1LL)] << endl;
    }

    return 0;
}

感想

どうやってグラフを作るかはすぐわかったが，$ 1 \leq c_i \leq M$とは限らないことに気づくまでにだいぶかかった．

NoiminのNoise

AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題概要

解法概要

ソースコード

感想