白準1753号[ダエストラ最短経路]

3683 ワード
コセット 白駿 テキストリンク

  • 東ビンナコテを準備する時、私が学んだアルゴリズムには、最短パスアルゴリズムに「distraアルゴリズム」があります.

  • 実際、これは動画や動画を見た後、自らディストラアルゴリズムを実施した後、2日後に復習の観点から解決した問題だ.

  • priority queueを使用する場合、(頂点、最短距離)paireオブジェクトに「最短距離」を基準にPQを挿入するために、3番目のパラメータにcustomcompare-しかし、他の人のコードを見て、ここではgreater>を直接使用することができます.

  • 現在の頂点の個数は1<=v<=20000であるため、改良されたdextraアルゴリズムを使用する必要がある.(繰り返しの場合は、論理的に非アクセスノードに最も近いノードを選択し、シーケンスナビゲーションではなく優先キューを使用します)

  • 注意:異なる2つの頂点の間に複数の幹線が存在する可能性があります.
    -いずれにしてもDirected Graphなので、Priority queueとして実施する場合はあまり注意すべき事項ではないようです
    -PQでfront()で取り出した要素は、d tableの距離値と比較して無視されるため、複数の幹線の中で最終的に最短距離となる幹線を選択する.

  • C++で書かれていても、運行時間は満足できません.
    • #include <iostream>
#include <queue>
#include <vector>
#include <time.h>


using namespace std;
typedef pair<int, int> Node; // (vertex번호, weight)  

struct customCompare {
	bool operator()(Node& n1, Node&n2)
	{
		return n1.second > n2.second;
	}
};

int nv, ne,start;
int infinity = 200000000;

vector<Node> graph[20001];
int d_table[20001];
//priority_queue<Node, vector<Node>, greater<Node>> q;
priority_queue<Node, vector<Node>, customCompare> q;



void dikstra()
{
	int i;
	d_table[start] = 0;
	q.push(Node(start, 0));
	
	while (q.empty() == false)
	{
		Node cur = q.top();
		int cur_d;
		q.pop();
		//이미 처리한 노드는 ignore
		if (d_table[cur.first] < cur.second) continue;

		//인접노드확인 
		for (i = 0; i < graph[cur.first].size();i++)
		{
			Node adj = graph[cur.first][i];
			cur_d = cur.second + adj.second;
			//update + push to queue as Node(adj.first, cur_d)
			if (cur_d < d_table[adj.first])
			{
				d_table[adj.first] = cur_d;
				q.push(Node(adj.first,cur_d)); 
			}
		}
	}



}
int main()
{
	cin >> nv >> ne >> start;

	for (int i = 0; i < ne; i++)
	{
		int v1, v2, w;
		cin >> v1 >> v2 >> w; 
		graph[v1].push_back({ v2,w }); 
	}

	for (int i = 0; i <= nv; i++)
		d_table[i] = infinity;
	
	dikstra();

	for (int i = 1; i <= nv; i++)
	{
		if (d_table[i] == infinity)printf("INF\n");
		else printf("%d\n", d_table[i]);
	}

}
    Ajaxとfetch API
    linux crontabは毎秒実行を実現