[白俊]1753号:最短経路
回答日:2021-07-04
質問する
質問する
質問リンク:https://www.acmicpc.net/problem/1753
アクセスと解析
これは最短経路を求める基本中の基本アルゴリズムDijkstraアルゴリズムを利用した問題である.
マルチフィーチャーラインアルゴリズムは、重み付け図から1つの開始ノード(始点)から始点を除くすべてのノードまでの最短距離を求めるアルゴリズムである.
優先キューを使用して次のナビゲートするノードを格納し、開始ノードから別のノードまでの距離を計算する配列を使用して最短距離を更新します.
マルチ翼点アルゴリズムについてよく視覚的に説明されているサイトを参照して、問題を解決します.
コード#コード# // 백준 1753번 : 최단경로
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
int dist[20001];
vector<pair<int, int>> road[200001];
void dijkstra(int start) {
dist[start] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
while(!pq.empty()) {
int distance = -pq.top().first;
int current = pq.top().second;
pq.pop();
if (dist[current] < distance) {
continue;
}
for (int i = 0; i < road[current].size(); i++) {
int next = road[current][i].first;
int nextDistance = distance + road[current][i].second;
if (nextDistance < dist[next]) {
dist[next] = nextDistance;
pq.push(make_pair(-nextDistance, next));
}
}
}
}
int main() {
int V, E, K;
cin >> V >> E >> K;
for (int i = 1; i <= V; i++) {
dist[i] = INF;
}
while(E--) {
int u, v, w;
cin >> u >> v >> w;
road[u].push_back(make_pair(v, w));
}
dijkstra(K);
for (int i = 1; i <= V; i++) {
if (dist[i] == INF) {
cout << "INF" << '\n';
} else {
cout << dist[i] << '\n';
}
}
return 0;
}
フィードバック
符号化テストを学習する過程で,マルチチャネルを利用する問題は退屈ではないことが分かった.アルゴリズムの授業でダエストラに関する知識を学んだが,概念が頭の中で曖昧になったため,関連問題を解決することにした.
Reference
この問題について([白俊]1753号:最短経路), 我々は、より多くの情報をここで見つけました
https://velog.io/@bestcoders/백준-1753번-최단경로
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
これは最短経路を求める基本中の基本アルゴリズムDijkstraアルゴリズムを利用した問題である.
マルチフィーチャーラインアルゴリズムは、重み付け図から1つの開始ノード(始点)から始点を除くすべてのノードまでの最短距離を求めるアルゴリズムである.
優先キューを使用して次のナビゲートするノードを格納し、開始ノードから別のノードまでの距離を計算する配列を使用して最短距離を更新します.
マルチ翼点アルゴリズムについてよく視覚的に説明されているサイトを参照して、問題を解決します.
コード#コード# // 백준 1753번 : 최단경로
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
int dist[20001];
vector<pair<int, int>> road[200001];
void dijkstra(int start) {
dist[start] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
while(!pq.empty()) {
int distance = -pq.top().first;
int current = pq.top().second;
pq.pop();
if (dist[current] < distance) {
continue;
}
for (int i = 0; i < road[current].size(); i++) {
int next = road[current][i].first;
int nextDistance = distance + road[current][i].second;
if (nextDistance < dist[next]) {
dist[next] = nextDistance;
pq.push(make_pair(-nextDistance, next));
}
}
}
}
int main() {
int V, E, K;
cin >> V >> E >> K;
for (int i = 1; i <= V; i++) {
dist[i] = INF;
}
while(E--) {
int u, v, w;
cin >> u >> v >> w;
road[u].push_back(make_pair(v, w));
}
dijkstra(K);
for (int i = 1; i <= V; i++) {
if (dist[i] == INF) {
cout << "INF" << '\n';
} else {
cout << dist[i] << '\n';
}
}
return 0;
}
フィードバック
符号化テストを学習する過程で,マルチチャネルを利用する問題は退屈ではないことが分かった.アルゴリズムの授業でダエストラに関する知識を学んだが,概念が頭の中で曖昧になったため,関連問題を解決することにした.
Reference
この問題について([白俊]1753号:最短経路), 我々は、より多くの情報をここで見つけました
https://velog.io/@bestcoders/백준-1753번-최단경로
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
// 백준 1753번 : 최단경로
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
int dist[20001];
vector<pair<int, int>> road[200001];
void dijkstra(int start) {
dist[start] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
while(!pq.empty()) {
int distance = -pq.top().first;
int current = pq.top().second;
pq.pop();
if (dist[current] < distance) {
continue;
}
for (int i = 0; i < road[current].size(); i++) {
int next = road[current][i].first;
int nextDistance = distance + road[current][i].second;
if (nextDistance < dist[next]) {
dist[next] = nextDistance;
pq.push(make_pair(-nextDistance, next));
}
}
}
}
int main() {
int V, E, K;
cin >> V >> E >> K;
for (int i = 1; i <= V; i++) {
dist[i] = INF;
}
while(E--) {
int u, v, w;
cin >> u >> v >> w;
road[u].push_back(make_pair(v, w));
}
dijkstra(K);
for (int i = 1; i <= V; i++) {
if (dist[i] == INF) {
cout << "INF" << '\n';
} else {
cout << dist[i] << '\n';
}
}
return 0;
}
符号化テストを学習する過程で,マルチチャネルを利用する問題は退屈ではないことが分かった.アルゴリズムの授業でダエストラに関する知識を学んだが,概念が頭の中で曖昧になったため,関連問題を解決することにした.
Reference
この問題について([白俊]1753号:最短経路), 我々は、より多くの情報をここで見つけました https://velog.io/@bestcoders/백준-1753번-최단경로テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol