[C++/規格]1916号:最低コスト取得

10332 ワード
cpp ダエストラ 白駿 テキストリンク

質問リンク
1916号:最低コストの取得
に答える
優先キューを使用するマルチタスクの問題
  • M個入力値がarrベクトルのstartインデックス中pair<end, distance>
  • ・dp・・출발 도시から인덱스 i 도시の間の最小距離のベクトルになりますが、まだ更新されていないので무한대値、출발 도시 인덱스に加入0
    • 使用
  • ・우선순위 큐の理由は、最短距離の都市から使用を開始し、pqエーpair<0, 출발 도시>を加えてpq賈許まで.
    3-1. distにpq.top().firstの負の値を加えます.(優先順位キューはデフォルトの降順なので、昇順で解く必要があります)
    3-2. dp[here]大きい場合dist更新不要continue3-3. 現在はhere接続されている都市(next)との距離を更新する必要があり、dp[next]賈dp[here]+nextDistを大きくするとより小さな距離に更新される.
    3-4. next接続された都市を更新するため、pqエpair<-nextDist, next>
    • コード#コード#
    #include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<pair<int, int>>> arr(n+1);
	vector<int> dp;

	for (int i = 0;i < m;i++) {
		int s, e, cost;
		cin >> s >> e >> cost;
		arr[s].push_back(make_pair(e, cost));
	}
	int stt, end;
	cin >> stt >> end;

	dp.resize(n + 1, 1000000000);
	
	dp[stt] = 0;

	priority_queue<pair<int,int>> pq;
	pq.push(make_pair(0, stt));

	while (!pq.empty()) {
		int dist = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		if (dp[here] < dist) continue;
		
		for (int i = 0;i < arr[here].size();i++) {
			int next = arr[here][i].first;
			int nextDist = arr[here][i].second;
			if (dp[next] > dp[here] + nextDist) {
				dp[next] = dp[here] + nextDist;
				pq.push(make_pair(-nextDist, next));
			}
		}
	}

	cout << dp[end];
	
	return 0;
}
    redisソースzmalloc.c実装
    asp.Netコレクションクラス