Mike and Shortcuts [Codeforces 361 : Div2 B]

問題

http://codeforces.com/contest/689/problem/B

n頂点あり、頂点間の遷移にかかるコストは以下の通り

• 頂点iから頂点jへの遷移は abs(i-j) のコストがかかる
• 頂点iから頂点aiへの遷移は 1 のコストがかかる

この時、頂点1から全頂点への最短コストを求めよ

1 <= n <= 200000

考察

1. 単一頂点からの最短距離なので、ダイクストラ感がでてる(制約もそれっぽい)
2. そこで困るのが、辺の数が多すぎるという所
3. 辺の数を減らすことを考える

4. 頂点1から頂点3への遷移はコスト2であるが、これは頂点1から頂点2への遷移のコストと頂点2から頂点3への遷移のコストの和と等しい
5. つまり絶対値を使った方のコストは隣り合う2頂点間にコスト1の辺を張るだけでOK
6. これで辺の数がどかんと減るので、計算がしやすくなる

7. これでダイクストラしても良いが、BFSを使う方がより良い（一緒かも？）
8. 全てのコストが1であるダイクストラは、実質BFSと同じである <- 要出典

9. なので頂点1からコストを1足しながらBFSをして、最後にそれを答える

実装

http://codeforces.com/contest/689/submission/18925897

int n;
int a[201010];
int ans[201010];
bool done[201010];
//-----------------------------------------------------------------
int main() {
	scanf("%d", &n);
	rep(i, 0, n) scanf("%d", &a[i]), a[i]--;

	queue<int> que;
	que.push(0);
	done[0] = true;
	while (!que.empty()) {
		int i = que.front(); que.pop();

		if (0 <= i) {
			if (!done[i - 1]) {
				ans[i - 1] = ans[i] + 1;
				done[i - 1] = true;
				que.push(i - 1);
			}
		}

		if (i < n - 1) {
			if (!done[i + 1]) {
				ans[i + 1] = ans[i] + 1;
				done[i + 1] = true;
				que.push(i + 1);
			}
		}

		if (!done[a[i]]) {
			ans[a[i]] = ans[i] + 1;
			done[a[i]] = true;
			que.push(a[i]);
		}
	}

	rep(i, 0, n) printf("%d ", ans[i]);
	printf("\n");
}