(BOJ)最短経路1753号

質問する

方向図が与えられている場合は、指定された開始点から他のすべての頂点への最短パスを解くプログラムを作成します.ただし、すべての幹線の重み付けは10以下の自然数です.

入力

第1行は頂点の個数Vと幹線の個数Eを与える.(1≦V≦20000,1≦E≦300000)すべての頂点が1〜Vの番号であると仮定する.2行目には、開始点の番号K(1≦K≦V)が与えられる.3行目から、各幹線を表す3つの整数(u,v,w)が順次与えられる.これはuからvまでの重み付けwの幹線が存在することを意味する.uとvは異なり,wは10以下の自然数である.異なる2つの頂点の間に複数の幹線が存在する可能性があることに注意してください.

しゅつりょく

最初の行からV行にまたがり、最初の行からi番頂点への最短パスのパス値を出力します.始点自体の出力は0であり、パスが存在しない場合はINFを出力すればよい.

トラブルシューティング

まず,問題において方向図を提案し,所与の開始点から他のすべての頂点への最短経路のソルバと呼ぶため,複数のアルゴリズムを用いる必要がある.
私が書いたいわゆるマルチアウトプットアルゴリズム...
1.始点から離れた矢印に関連する頂点を見つけ、重み付き値をその頂点の値として保存します.
2.配列に格納されている最小ウェイトの頂点を検索します.この角度から言えば、一つの頂点にアクセスしたと言える.(ただし、1のプロセスの頂点でなければなりません.)
3.見つかった(アクセスした)頂点から外矢印への接続頂点を見つけ、見つけた各頂点間の重み付けと外矢印で接続した頂点間の重み付けを求める.
未保存値

上記で求めた値は、配列に対応するインデックス(矢印に関連付けられた頂点)の値として格納されます.

値が保存されている場合
配列内の対応するインデックスの値(重み)を上で求めた値と比較し、求めた値がより小さい場合はそのインデックスの値を更新します.これは、矢印接続の頂点に達するためには、より小さな費用で本人が到着する必要があることを意味します.

重み付け値が決定された頂点に加えて、最小重み付け値を持つ頂点を探します.

すべての頂点の重みが決まるまで、3と4の手順を繰り返します.ここで,本人は方向図を実現するために「データ型がベクトルの配列」を生成し,「優先キュー」を用いて多解像度アルゴリズムを実現する.
本人はJavaでグラフを実現する際、「資料型はリストの並び」をよく使います.左と同じグラフィックと右と同じ…!

アルゴリズムの授業で、C++はベクトルを提供すると、見つけて書きました.

#include <vector>

struct Node {
	int key;
	int value;

	Node(int k, int v) : key(k), value(v) {

	}
};

int main(){
	vector<Node> graph[20001];
	return 0;
}

グラフィック頂点と重み付けを含む構造体ノードを作成し,ノードベクトルが資料型の配列を作成した.(Vは最大20,000なので、大きさは2,001とします.)
開始点から特定のポイントへの最小重み付け値を求める優先キューが必要になります.

#include <queue>

struct Sort {
	bool operator()(Node a, Node b) {
		return a.value > b.value;
	}
};

int main(){
	priority_queue<Node, vector<Node>, Sort> pq; // 우선순위 큐
    	int weight[20001]; // 정답 배열
	return 0;
}

また,始点から本人の頂点までの最小重みを格納する配列重みも生成した.
頂点と最小重み付け値を含むノードを優先キューに追加し、重み付け基準で並べ替え、重み付けの小さいノードを前に移動します.アクセスされていない頂点で最小重み付け値を持つ頂点を見つけることができると考えているからです.

weight[startNum] = 0; // 첫 번째 정점 가중치 0
	pq.push(Node(startNum, 0));

 	while (!pq.empty()) {
		Node n = pq.top();
		pq.pop();

		int key = n.key;
		int value = n.value;

			for (int i = 0; i < graph[key].size(); i++) {
				Node tempNode = graph[key].at(i);
				
				int nextVal = value + tempNode.value;
				if (weight[tempNode.key] == -1 || (nextVal < weight[tempNode.key])) { // 방문하지 않은 점이나 갱신될 점의 가중치가 더 작은 경우
					weight[tempNode.key] = nextVal;
					tempNode.value = nextVal; // 가중치를 누적시킨 후 큐에 삽입
					pq.push(tempNode);
				}
			}
	}

優先キューからノードを削除すると,その頂点にアクセスすると考えられ,その頂点から進行方向の頂点を調べた.
1)進行方向の頂点にアクセスしたことがない場合
2)重み配列内の対応するインデックスの値(これまでの最小重み)と、自身の重みに自身と新しい頂点との間の重みを加えた値を比較します.
1)および2)いずれかが適切であれば,いずれも更新の過程を経ており,更新すると頂点と最小重み付けを含むノードを優先順位キューに入れる.この場合、重み付け値は、2つの頂点間の重み付け値ではなく、本人と新しい頂点間の重み付け値であるべきである.
どうして.
優先キューからノードを削除
=頂点へのアクセス
=頂点の最小重み付けが決定されます
したがって、少なくとも優先順位キューにおける重み付け値は本人の重み付け値であり、接続点を決定する最小重み付け値にも影響する.
1)と2)でなければ?優先順位キューに配置する必要はありません.訪問した実績があれば、本人を通さずにもっと速く歩け、これ以上調べる必要はありません.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Node {
	int key;
	int value;

	Node(int k, int v) : key(k), value(v) {

	}
};

struct Sort {
	bool operator()(Node a, Node b) {
		return a.value > b.value;
	}
};

int main() {
	priority_queue<Node, vector<Node>, Sort> pq;
	vector<Node> graph[20001];
	int weight[20001];
	int v;
	int e;
	int startNum;
	cin >> v;
	cin >> e;
	cin >> startNum;


	for (int i = 1; i <= v; i++) {
		weight[i] = -1;
	}

	for (int i = 0; i < e; i++) {
		int start;
		int end;
		int val;

		cin >> start >> end >> val;
		graph[start].push_back(Node(end, val));
	}

	weight[startNum] = 0; // 첫 번째 정점 가중치 0
	pq.push(Node(startNum, 0));

 	while (!pq.empty()) {
		Node n = pq.top();
		pq.pop();

		int key = n.key;
		int value = n.value;

			for (int i = 0; i < graph[key].size(); i++) {
				Node tempNode = graph[key].at(i);
				
				int nextVal = value + tempNode.value;
				if (weight[tempNode.key] == -1 || (nextVal < weight[tempNode.key])) { // 방문하지 않은 점이나 갱신될 점의 가중치가 더 작은 경우
					weight[tempNode.key] = nextVal;
					tempNode.value = nextVal; // 가중치를 누적시킨 후 큐에 삽입
					pq.push(tempNode);
				}
			}
	}

	for (int i = 1; i <= v; i++) {
		if (weight[i] == -1) {
			cout << "INF" << '\n';
		}
		else {
			cout << weight[i] << '\n';
		}
	}
	
	return 0;
}

コード全体がそうです.
ちょっと待って.優先キューからノードを削除した瞬間、頂点に無条件にアクセスしますか...?すべての頂点にアクセスする前はそうですが、後ろから減算されたノードではそうではありません.ノードが多ければ多いほど、1つの頂点の重みが更新される可能性があります.したがって、優先キュー内のノードが入る回数は、頂点の数よりもほとんど多くなります.コードにはこのような対策はありませんが、優先キューから頂点の数でノードを削除すると、終了などの措置をとることができます.
(かなり違うと思いますが…)