mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 052 C - 高橋くんと不思議な道

解法

まず自明な解法として, d[v][b] = (頂点 v までに, b 回タイプ B の道を通る場合の最短距離)というのがあります。

b は N より大きかったらどこかの頂点を複数回通っていることになるので, 頂点の個数は O(N^2) でダイクストラをすれば良いです。

これだともちろん TLE, MLE をするんですが, これを工夫することで解が得られます。

need[v] = (頂点 v まで行くのに最低限必要な B の辺の本数)というのを前計算しておきます。
すると, need[v] よりも SIZE = 1.5*sqrt(N) 本以上余計に B の辺を通ることは無駄であることがわかります(というのは, かかるコストは 1/2*(1+need[v])*need[v] + (タイプ A の辺を通る数) < 1/2*(1+need[v])*need[v] + N であるので, もし need[v] よりも余計に SIZE 本以上 B を通ると先述の上限よりも解が大きくなってしまうので)。

よって, 探索すべき b の範囲が need[v] <= b <= need[v]+SIZE とわかったので, これらのところのみダイクストラで計算すれば良いです。

struct edge {
    int v;
    int 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 = 100100;
const int MAXN = 10010;
const int SIZE = 150;
int C[MAXM], A[MAXM], B[MAXM];
int need[MAXN];
int N, M;

int getV(int v, int b) {
	return b*N+v;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    	cin >> C[i] >> A[i] >> B[i];
    // 絶対に通らなければならない B の辺の本数の最小値を求める
    vector<vector<edge> > G(N);
    for (int i = 0; i < M; i++) {
    	G[A[i]].emplace_back(B[i], C[i]);
    	G[B[i]].emplace_back(A[i], C[i]);
    }
    {
    	auto d = dijkstra(N, G, 0);
    	for (int i = 0; i < N; i++) 
    		need[i] = d[i];
    }
    // ダイクストラ
    vector<ll> d(N*SIZE, LLONG_MAX/10); d[0] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, 0));
    while (!que.empty()) {
    	auto p = que.top(); que.pop();
    	int u = p.second;
    	int b = u/N, v = u%N;
    	ll dist = -p.first;
    	if (dist > d[u]) continue;
    	for (edge e : G[v]) {
    		if (need[v]+b+e.w-need[e.v] < SIZE) {
    			int next = getV(e.v, need[v]+b+e.w-need[e.v]);
    			if (d[next] > d[u]+(e.w==0 ? 1 : need[v]+b+1)) {
    				d[next] = d[u]+(e.w==0 ? 1 : need[v]+b+1);
    				que.push(make_pair(-d[next], next));
    			}
    		}
    	}
    }
    for (int i = 0; i < N; i++) {
    	ll ans = 1ll<<60;
    	for (int j = 0; j < SIZE; j++)
    		ans = min(ans, d[getV(i, j)]);
    	cout << ans << endl;
    }
    return 0;
}