ICPCアジア地区筑波大会2015 I問題 : Routing a Marathon Race

問題. Routing a Marathon Race

無向グラフ ，2頂点 ，頂点重み が与えられる． から へのコスト最小の道を見つけそのコストを答えよ．ただし，道のコストとはその道に含まれる頂点の重み和と，道に少なくとも1頂点が隣接する道以外の頂点の重み和を足したものである．

制約： ，　

解法. 全列挙

から への道を枝刈りを行いながら全探索する． から頂点 への道を として， に含まれない頂点で， に隣接する頂点全体を とする．このとき， 以降で訪れる頂点の候補は と に属する頂点以外である．なぜならば， と に含まれる頂点は既に道 のコストに含まれており，また の途中で訪れることができたので今後訪れることでコストが最小になることはないからである．この性質は一般の最短路問題でも成立つ性質である．
最悪ケースはグラフが完全二分木のときで，木の高さを として としたとき， を満たすので となる．したがって，計算時間は である．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> c, visited;
vector<vector<int>> adj;

int Dfs(int cur) {
    if (cur == n - 1) {
        int res = 0;
        for (int dst : adj[cur]) if (visited[dst] == -1) res += c[dst];
        return res;
    }

    int res = 0;
    for (int dst : adj[cur]) {
        if (visited[dst] == -1) {
            visited[dst] = cur;
            res += c[dst];
        }
    }

    int d = INT_MAX;
    for (int dst : adj[cur])
        if (visited[dst] == cur) d = min(d, Dfs(dst));

    for (int dst : adj[cur])
        if (visited[dst] == cur) visited[dst] = -1;

    return (INT_MAX <= d ? d : res + d);
}

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

    cin >> n >> m;
    c.resize(n); visited.resize(n, -1); adj.resize(n);
    for (int v = 0; v < n; ++v) cin >> c[v];
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }

    visited[0] = -2;
    cout << Dfs(0) + c[0] << endl;

    return 0;
}

まとめ

計算時間の解析が難しい．たぶん正しいはず・・・．
自信がないので後で修正．