ダエストラ
12023 ワード
要害
:次の原価を計算するのは、現在からお客様の原価と
外部入力のコストを加算し、dist値と比較します.
この部分が一番重要です.
1～4～3のコストは、1～3のコストよりも小さくなります./
マルチアウトプットアルゴリズムとは?
:ある場所から別の場所へのアルゴリズム.
ステージ
1)開始点を0、残りの頂点を無限に設定します.
1−1)始点から接続頂点までの距離を記憶空間に入れる.
2)頂点のうちチェックされていない頂点の中で最も値の小さい頂点をチェックし、
頂点から移動できるすべての頂点の値を更新します.
更新時にターゲット位置の値と
接続頂点の現在の保存値を比較します.
現在の値を更新値と比較して、更新するかどうかを決定します.
現在の値と更新値の最小値を適用します.
3)作業を2回繰り返す.
1)開始点を0、残りの頂点を無限に設定します.
1−1)始点から接続頂点までの距離を記憶空間に入れる.
2)頂点のうちチェックされていない頂点の中で最も値の小さい頂点をチェックし、
頂点から移動できるすべての頂点の値を更新します.
更新時にターゲット位置の値と
接続頂点の現在の保存値を比較します.
現在の値を更新値と比較して、更新するかどうかを決定します.
現在の値と更新値の最小値を適用します.
3)作業を2回繰り返す.
2号任務における疑念を証明する
->疑わしい点は、チェックされた頂点のシーケンスを再確認することができず、別の頂点を通過する場合、4番ノードの値を最短距離に更新できるかどうかを考慮することです.
しかし、それを証明する条件があります.
1番の頂点が完成したら、2、3、4、5、6番の頂点の中で最も距離の小さい頂点を選択します.
この用語は、それ以外の値は、4番目の頂点に入ると、より低い値にはならないことを意味する.距離は正数なので.
距離が負数であれば、この証明は間違っています.
確認しよう
更新後、4番以下の値1は指定できません.
->別の頂点が接続されていると仮定し、5番が接続されていると仮定します.
これは、チェックされていない頂点の中で最も小さい頂点(現在4番は1)であるためです.
5番はもう一つの頂点に1秒を超えた値になるはずです!確認できるため、4番の値はより低い値に更新できません.
考察する
:コードの作成方法
pairを利用しよう
優先度キュー、top()は低設定でなければなりません.
だから
:コードを見ると、最初に優先キューに入れたときに負の値に入れます.
質問する
:230ページ目と同じ画像を与え、249ページ目と同じ入力を与えた場合、各頂点までの最短距離はどのくらいですか.
絵をかく
本の例を参照:249ページ
ソース-このチュートリアルのコード #include <iostream>
#include <vector>
#include <queue>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];
void dijkstra(int start) {
priority_queue<pair<int, int> > pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({ 0, start });
d[start] = 0;
while (!pq.empty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
int dist = -pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
//210806 이부분 이해하는 것이 중요함.
//정점의 테이블 값보다 값이 크다면 밑의 반복문을 할 필요가 없다.
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({ b, c });
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}
ソースコード-比較関数を使用するコード #include <iostream>
#include <vector>
#include <queue>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];
//거리가 가장 작은 놈이 top으로 와야 한다..
struct comp
{
bool operator()(pair<int, int>a, pair<int, int>b)
{
return a.first > b.first;
}
};
void dijkstra(int start) {
priority_queue<pair<int, int>, vector<pair<int,int>>, comp > pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({ 0, start });
d[start] = 0;
while (!pq.empty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
int dist = pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
//210806 이부분 이해하는 것이 중요함.
//정점의 테이블 값보다 값이 크다면 밑의 반복문을 할 필요가 없다.
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(cost, graph[now][i].first));
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({ b, c });
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}
上図に示すように、1番ノードから各頂点への最小コストを出力します。
その他の入力
6 11
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
その他の出力
0
2
3
1
2
4
ソースコード-不変量を使用 #include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
//정점마다 연결되어 있는 정점들이 있을 수도 있고, 없을 수도 있고, 표현하기 위해서
//벡터의 배열을 사용한 것이다.
vector<pair<int, int>>v[21];
bool checked[21] = { 0, };
//dp 테이블이라고 생각하면 된다.
//시작점에서 모든 정점까지 가는데의 거리 비용을 나타낸다.
//시작점을 기준으로 해서 확인하는 것이 아니므로 dist는 1차원 벡터를 사용하는 것이다.
vector<int>dist(21, 100000);
//거리가 가장 작은 놈이 top으로 와야 한다..
struct cmp
{
bool operator()(pair<int, int>a, pair<int, int>b)
{
return a.first > b.first;
}
};
void daikstra(int start)
{
//first를 비용, second를 다음 정점으로 하자.
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>pq;
dist[start] = 0;
pq.push({ 0,start });
while (!pq.empty())
{
int curV = pq.top().second;
int curCost = pq.top().first;
pq.pop();
//이미 거쳤음!
if (checked[curV] == true)
continue;
//한번 탐색 완료된 정점 체크하기
//불변수를 사용할 경우
checked[curV] = true;
//연결되어 있는 모든 정점을 확인해서 가장 cost가 적은 것을 우선순위의 top에다가 위치하자.
for (int i = 0; i < v[curV].size(); i++)
{
int targetCost = curCost + v[curV][i].second;
if (targetCost > dist[v[curV][i].first])
continue;
int targetV = v[curV][i].first;
//갱신하기
dist[v[curV][i].first] = targetCost;
pq.push({ targetCost , targetV });
}
}
}
int main(void) {
int n, m;
cin >> n >> m;
//정점 - 도착점 - 비용
//동일한 정점에서만 탐색을 해야 하므로 벡터를 배열 형식으로 사용함.
//1. 이해해야 할점.
//각 정점에 연결된 다른 정점들의 정보를 알고 있어야 하므로
//벡터를 배열 형태로 사용하고 (도착점, 거리비용)
//2. 이해해야 할점.
//최종 거리를 알기 위해서 벡터를 사용한다.
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({ b,c });
}
daikstra(1);
cout << "1번 정점에서 다른 정점으로 가는데 걸리는 최소 비용" << endl;
for (int i = 1; i < 21; i++)
cout << dist[i] << " ";
return 0;
}
入力
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
しゅつりょく
2 : 11
3 : 4
4 : 9
5 : 14
Reference
この問題について(ダエストラ), 我々は、より多くの情報をここで見つけました
https://velog.io/@kwt0124/다익스트라
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];
void dijkstra(int start) {
priority_queue<pair<int, int> > pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({ 0, start });
d[start] = 0;
while (!pq.empty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
int dist = -pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
//210806 이부분 이해하는 것이 중요함.
//정점의 테이블 값보다 값이 크다면 밑의 반복문을 할 필요가 없다.
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({ b, c });
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];
//거리가 가장 작은 놈이 top으로 와야 한다..
struct comp
{
bool operator()(pair<int, int>a, pair<int, int>b)
{
return a.first > b.first;
}
};
void dijkstra(int start) {
priority_queue<pair<int, int>, vector<pair<int,int>>, comp > pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({ 0, start });
d[start] = 0;
while (!pq.empty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
int dist = pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
//210806 이부분 이해하는 것이 중요함.
//정점의 테이블 값보다 값이 크다면 밑의 반복문을 할 필요가 없다.
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(cost, graph[now][i].first));
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({ b, c });
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}上図に示すように、1番ノードから各頂点への最小コストを出力します。
その他の入力
6 11
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
その他の出力
0
2
3
1
2
4
ソースコード-不変量を使用 #include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
//정점마다 연결되어 있는 정점들이 있을 수도 있고, 없을 수도 있고, 표현하기 위해서
//벡터의 배열을 사용한 것이다.
vector<pair<int, int>>v[21];
bool checked[21] = { 0, };
//dp 테이블이라고 생각하면 된다.
//시작점에서 모든 정점까지 가는데의 거리 비용을 나타낸다.
//시작점을 기준으로 해서 확인하는 것이 아니므로 dist는 1차원 벡터를 사용하는 것이다.
vector<int>dist(21, 100000);
//거리가 가장 작은 놈이 top으로 와야 한다..
struct cmp
{
bool operator()(pair<int, int>a, pair<int, int>b)
{
return a.first > b.first;
}
};
void daikstra(int start)
{
//first를 비용, second를 다음 정점으로 하자.
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>pq;
dist[start] = 0;
pq.push({ 0,start });
while (!pq.empty())
{
int curV = pq.top().second;
int curCost = pq.top().first;
pq.pop();
//이미 거쳤음!
if (checked[curV] == true)
continue;
//한번 탐색 완료된 정점 체크하기
//불변수를 사용할 경우
checked[curV] = true;
//연결되어 있는 모든 정점을 확인해서 가장 cost가 적은 것을 우선순위의 top에다가 위치하자.
for (int i = 0; i < v[curV].size(); i++)
{
int targetCost = curCost + v[curV][i].second;
if (targetCost > dist[v[curV][i].first])
continue;
int targetV = v[curV][i].first;
//갱신하기
dist[v[curV][i].first] = targetCost;
pq.push({ targetCost , targetV });
}
}
}
int main(void) {
int n, m;
cin >> n >> m;
//정점 - 도착점 - 비용
//동일한 정점에서만 탐색을 해야 하므로 벡터를 배열 형식으로 사용함.
//1. 이해해야 할점.
//각 정점에 연결된 다른 정점들의 정보를 알고 있어야 하므로
//벡터를 배열 형태로 사용하고 (도착점, 거리비용)
//2. 이해해야 할점.
//최종 거리를 알기 위해서 벡터를 사용한다.
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({ b,c });
}
daikstra(1);
cout << "1번 정점에서 다른 정점으로 가는데 걸리는 최소 비용" << endl;
for (int i = 1; i < 21; i++)
cout << dist[i] << " ";
return 0;
}
入力
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
しゅつりょく
2 : 11
3 : 4
4 : 9
5 : 14
Reference
この問題について(ダエストラ), 我々は、より多くの情報をここで見つけました
https://velog.io/@kwt0124/다익스트라
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
6 11
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
その他の出力
0
2
3
1
2
4
ソースコード-不変量を使用 #include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
//정점마다 연결되어 있는 정점들이 있을 수도 있고, 없을 수도 있고, 표현하기 위해서
//벡터의 배열을 사용한 것이다.
vector<pair<int, int>>v[21];
bool checked[21] = { 0, };
//dp 테이블이라고 생각하면 된다.
//시작점에서 모든 정점까지 가는데의 거리 비용을 나타낸다.
//시작점을 기준으로 해서 확인하는 것이 아니므로 dist는 1차원 벡터를 사용하는 것이다.
vector<int>dist(21, 100000);
//거리가 가장 작은 놈이 top으로 와야 한다..
struct cmp
{
bool operator()(pair<int, int>a, pair<int, int>b)
{
return a.first > b.first;
}
};
void daikstra(int start)
{
//first를 비용, second를 다음 정점으로 하자.
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>pq;
dist[start] = 0;
pq.push({ 0,start });
while (!pq.empty())
{
int curV = pq.top().second;
int curCost = pq.top().first;
pq.pop();
//이미 거쳤음!
if (checked[curV] == true)
continue;
//한번 탐색 완료된 정점 체크하기
//불변수를 사용할 경우
checked[curV] = true;
//연결되어 있는 모든 정점을 확인해서 가장 cost가 적은 것을 우선순위의 top에다가 위치하자.
for (int i = 0; i < v[curV].size(); i++)
{
int targetCost = curCost + v[curV][i].second;
if (targetCost > dist[v[curV][i].first])
continue;
int targetV = v[curV][i].first;
//갱신하기
dist[v[curV][i].first] = targetCost;
pq.push({ targetCost , targetV });
}
}
}
int main(void) {
int n, m;
cin >> n >> m;
//정점 - 도착점 - 비용
//동일한 정점에서만 탐색을 해야 하므로 벡터를 배열 형식으로 사용함.
//1. 이해해야 할점.
//각 정점에 연결된 다른 정점들의 정보를 알고 있어야 하므로
//벡터를 배열 형태로 사용하고 (도착점, 거리비용)
//2. 이해해야 할점.
//최종 거리를 알기 위해서 벡터를 사용한다.
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({ b,c });
}
daikstra(1);
cout << "1번 정점에서 다른 정점으로 가는데 걸리는 최소 비용" << endl;
for (int i = 1; i < 21; i++)
cout << dist[i] << " ";
return 0;
}
入力
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
しゅつりょく
2 : 11
3 : 4
4 : 9
5 : 14
Reference
この問題について(ダエストラ), 我々は、より多くの情報をここで見つけました
https://velog.io/@kwt0124/다익스트라
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
//정점마다 연결되어 있는 정점들이 있을 수도 있고, 없을 수도 있고, 표현하기 위해서
//벡터의 배열을 사용한 것이다.
vector<pair<int, int>>v[21];
bool checked[21] = { 0, };
//dp 테이블이라고 생각하면 된다.
//시작점에서 모든 정점까지 가는데의 거리 비용을 나타낸다.
//시작점을 기준으로 해서 확인하는 것이 아니므로 dist는 1차원 벡터를 사용하는 것이다.
vector<int>dist(21, 100000);
//거리가 가장 작은 놈이 top으로 와야 한다..
struct cmp
{
bool operator()(pair<int, int>a, pair<int, int>b)
{
return a.first > b.first;
}
};
void daikstra(int start)
{
//first를 비용, second를 다음 정점으로 하자.
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>pq;
dist[start] = 0;
pq.push({ 0,start });
while (!pq.empty())
{
int curV = pq.top().second;
int curCost = pq.top().first;
pq.pop();
//이미 거쳤음!
if (checked[curV] == true)
continue;
//한번 탐색 완료된 정점 체크하기
//불변수를 사용할 경우
checked[curV] = true;
//연결되어 있는 모든 정점을 확인해서 가장 cost가 적은 것을 우선순위의 top에다가 위치하자.
for (int i = 0; i < v[curV].size(); i++)
{
int targetCost = curCost + v[curV][i].second;
if (targetCost > dist[v[curV][i].first])
continue;
int targetV = v[curV][i].first;
//갱신하기
dist[v[curV][i].first] = targetCost;
pq.push({ targetCost , targetV });
}
}
}
int main(void) {
int n, m;
cin >> n >> m;
//정점 - 도착점 - 비용
//동일한 정점에서만 탐색을 해야 하므로 벡터를 배열 형식으로 사용함.
//1. 이해해야 할점.
//각 정점에 연결된 다른 정점들의 정보를 알고 있어야 하므로
//벡터를 배열 형태로 사용하고 (도착점, 거리비용)
//2. 이해해야 할점.
//최종 거리를 알기 위해서 벡터를 사용한다.
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({ b,c });
}
daikstra(1);
cout << "1번 정점에서 다른 정점으로 가는데 걸리는 최소 비용" << endl;
for (int i = 1; i < 21; i++)
cout << dist[i] << " ";
return 0;
}
入力
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5
しゅつりょく
2 : 11
3 : 4
4 : 9
5 : 14
Reference
この問題について(ダエストラ), 我々は、より多くの情報をここで見つけました
https://velog.io/@kwt0124/다익스트라
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
2 : 11
3 : 4
4 : 9
5 : 14
Reference
この問題について(ダエストラ), 我々は、より多くの情報をここで見つけました https://velog.io/@kwt0124/다익스트라テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol