[BOJ]13907税金

[正解ではなく解答記録]
税金賦課
多くの都市が道路でつながっている.道路間の通行料があって、すべての道路の通行料がK次KIの時、S都市からD都市までの最初の最小費用と値上げ後の最小費用はいくらですか?

に近づく

都市間道路は双方向道路である.

の木構造ではなく、都市間に2つの通行料がある可能性があります.

通行料の引き上げはすべての道路に適用されます.

が上昇した後、最低コストを再獲得するのに十分な時間がありません.

インプリメンテーション

税金をかける

増税はすべての道路(以下、幹線と略称する)に適用される.
考えてみれば、最小コストの増分は、最小コストを実現するために通過する幹線の数に応じて変化する.
これは、最も低コストの経路が通過する幹線が多い場合、上昇すると最も低コストの経路が最も低コストの経路に変更され、他の通過する幹線が少ない経路が最も低コストの経路になることを意味する.
そのため、私たちが通過する幹線の数は最小料金を別途求めなければなりません.
配列を作成した場合、通常の最低コスト(D[ノード数])と同等のコストが表示されます.
この問題では、D「通過する幹線数」「ノード数」を作成して、この通過する幹線数を反映します.

最小コストの取得

最小コストを求める場合は、優先順位キューを{コスト、{通過する幹線数、ノード番号}}に設定します.
まず優先順位キューに{0,{0,および開始点}}を入れ,複数のストライプで検索する.
STL優先キューは降順なのでgreatを使用して昇順に変更する必要があります.

while (!pq.empty()) {
		int node = pq.top().second.second;//노드 번호
		long long value = pq.top().first;//비용
		int Count = pq.top().second.first;//통과한 간선의 수
		pq.pop();

		if (D[Count][node] < value) {
			continue;
		}

		for (int i = 0; i < v[node].size(); i++) {
			if (D[Count + 1][v[node][i].first] > value + v[node][i].second) {
				D[Count + 1][v[node][i].first] = value + v[node][i].second;
				pq.push({ D[Count + 1][v[node][i].first],{Count+1,v[node][i].first}});
			}
		}
	}

答え探して

アップグレード前の最低コストを印刷し、アップグレードのたびに答えを印刷する必要があります.
通過する幹線の数が異なり、コストも異なるため、for文で最小値を検索する必要があります.
アップ前のコストはforを迂回し、D[i]「到達点ノード」の最小値を検索することです.
アップされたコストはforで、D[i]「到達ノード」にi*(アップコスト)を追加し、最小値を探します.

long long Min = MAX;
	for (int j = 1; j <= n; j++) {
		Min = min(Min, D[j][e]);
	}
	printf("%lld\n", Min);
	for (int i = 1; i <= k; i++) {
		scanf("%d",&a);
		Min = MAX;
		for (int j = 1; j <= n; j++) {
			D[j][e] += (j*a);
			Min = min(Min, D[j][e]);
		}
		printf("%lld\n", Min);
	}

の最後の部分

思い出してみると通過する幹線の数によって増額される料金も違ってくるので解けると思います.
終わりだ!