CODE THANKS FESTIVAL 2015 G - カメレオン

問題

code-thanks-festival-2015-open.contest.atcoder.jp

解法

基本的な方針は(頂点, 色)の組でまとめた頂点に対するグラフについてダイクストラやるだけです。ただ, 少し工夫しないと計算量やメモリが大変なことになるので少し工夫します。

工夫1: (頂点, 色) の組は, 頂点が接続している辺で関係する色以外は知らなくて良い(ただし頂点 1 だけは はじめの色として色 1 を覚えておかないとダメ)
工夫2: 同じ頂点で色を変えることを考えて辺を結ばないと行けないが, 頂点 v に C 種類の色があるとすると, 結ばなければならない辺の数は C-1 個で良い
工夫3: (頂点, 色) の組は, map で管理すると dijkstra のライブラリと対応させやすい？(個人の感想です)

typedef pair<int, int> pii;

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

const int MAXM = 800040;
const int MAXN = 400040;
int a[MAXM], b[MAXM];
ll c[MAXM], t[MAXM];
vector<ll> color[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    map<pii, int> m;
    m[pii(0, 1)] = 0;
    color[0].push_back(1);
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i] >> c[i] >> t[i];
        a[i]--; b[i]--;
        color[a[i]].push_back(c[i]);
        color[b[i]].push_back(c[i]);
        m[pii(a[i], c[i])] = 0;
        m[pii(b[i], c[i])] = 0;
    }
    int V = 0;
    for (auto& p : m) {
        p.second = V++;
    }
    vector<vector<edge> > G(V);
    for (int i = 0; i < N; i++) {
        sort(color[i].begin(), color[i].end());
        color[i].erase(unique(color[i].begin(), color[i].end()), color[i].end());
        int size = color[i].size();
        for (int j = 0; j < size-1; j++) {
            int v = m[pii(i, color[i][j])], u = m[pii(i, color[i][j+1])];
            G[v].emplace_back(u, color[i][j+1]-color[i][j]);
            G[u].emplace_back(v, color[i][j+1]-color[i][j]);
        }
    }
    for (int i = 0; i < M; i++) {
        int v = m[pii(a[i], c[i])], u = m[pii(b[i], c[i])];
        G[v].emplace_back(u, t[i]);
        G[u].emplace_back(v, t[i]);
    }
    auto d = dijkstra(V, G, m[pii(0, 1)]);
    ll ans = 1ll<<55;
    for (auto p : m) {
        if (p.first.first != N-1) continue;
        ans = min(ans, d[p.second]);
    }
    cout << ans << endl;
    return 0;
}