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

問題ページ - E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

概要

個の駅があり、本の地下鉄路線がこれらの駅間を結んでいる。番目の路線は駅と駅の間を結び、会社によって運営されている。地下鉄の運賃は、同じ会社の路線に乗り続ける場合は距離にかかわらずであり、他社の路線に乗り換える度に新たにかかる。また、一度他社の路線に乗り換えると、再度元の会社に戻っても別運賃となる。駅から駅まで行くときの最小の運賃を求めよ。ただし、地下鉄のみで到達できない場合はを出力せよ。

制約

入力はすべて整数

解法

今いる駅番号と最後に使った会社の組を頂点として考える。また、最後に使った会社が0のとき改札外、そうでないときはその番号の会社の改札内にいると考える。pair型を頂点としたいので、グラフやコストはstd::mapを使って持つ。与えられる路線とは別に、改札内外を行き来する辺を張る。辺のコストは、改札外から改札内に行く辺をとし、路線と改札内から改札外へ行く辺をとする。これで運賃の処理が可能となる。あとはダイクストラ法や01BFSなどを使えば、この問題を解ける

提出コード

ダイクストラ法

https://atcoder.jp/contests/arc061/submissions/4344465

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

const int IINF = 1e9 + 100;

struct edge{
    pair<int, int> to;
    int cost;
};

struct node{
    pair<int, int> v;
    int cost;

    bool operator<(const node & right) const {
        return cost > right.cost;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    map<pair<int, int>, vector<edge> > g;
    for(int i = 0 ; i < m ; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        g[{a, c}].push_back({{b, c}, 0});
        g[{b, c}].push_back({{a, c}, 0});
        g[{a, c}].push_back({{a, 0}, 0});
        g[{a, 0}].push_back({{a, c}, 1});
        g[{b, c}].push_back({{b, 0}, 0});
        g[{b, 0}].push_back({{b, c}, 1});
    }

    map<pair<int, int>, int> cost;
    for(auto x : g){
        cost[x.first] = IINF;
    }
    cost[{n - 1, 0}] = IINF;

    priority_queue<node> que;
    que.push({{0, 0}, 0});
    while(!que.empty()){
        node now = que.top();
        que.pop();
        if(cost[now.v] <= now.cost){
            continue;
        }
        cost[now.v] = now.cost;
        for(auto x : g[now.v]){
            if(cost[x.to] > now.cost + x.cost){
                que.push({x.to, now.cost + x.cost});
            }
        }
    }

    if(cost[{n - 1, 0}] < IINF){
        cout << cost[{n - 1, 0}] << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}

01BFS

https://atcoder.jp/contests/arc061/submissions/4344490

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

const int IINF = 1e9 + 100;

struct edge{
    pair<int, int> to;
    int cost;
};

struct node{
    pair<int, int> v;
    int cost;

    bool operator<(const node & right) const {
        return cost > right.cost;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    map<pair<int, int>, vector<edge> > g;
    for(int i = 0 ; i < m ; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        g[{a, c}].push_back({{b, c}, 0});
        g[{b, c}].push_back({{a, c}, 0});
        g[{a, c}].push_back({{a, 0}, 0});
        g[{a, 0}].push_back({{a, c}, 1});
        g[{b, c}].push_back({{b, 0}, 0});
        g[{b, 0}].push_back({{b, c}, 1});
    }

    map<pair<int, int>, int> cost;
    for(auto x : g){
        cost[x.first] = IINF;
    }
    cost[{n - 1, 0}] = IINF;

    deque<node> deq;
    deq.push_back({{0, 0}, 0});
    while(!deq.empty()){
        node now = deq.front();
        deq.pop_front();
        if(cost[now.v] <= now.cost){
            continue;
        }
        cost[now.v] = now.cost;
        for(auto x : g[now.v]){
            if(cost[x.to] > now.cost + x.cost){
                if(x.cost == 0){
                    deq.push_front({x.to, now.cost});
                }else{
                    deq.push_back({x.to, now.cost + x.cost});
                }
            }
        }
    }

    if(cost[{n - 1, 0}] < IINF){
        cout << cost[{n - 1, 0}] << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}