🙇‍♀️다익스트라 알고리즘

아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로그램을 작성하세요. (경로가 없으면 Impossible를 출력한다)

가중치 방향 그래프

▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 

그 다음부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다.

▣ 출력설명
1번 정점에서 각 정점으로 가는 최소 비용을 2번 정점부터 차례대로 출력하세요.

▣ 입력예제 1 
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

▣ 출력예제 1
2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible

🚀풀이

다익스트라 알고리즘!

기록용

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge
{
	int v;
	int dist;

	bool operator<(const Edge& other) const
	{
		return dist > other.dist;
	}
};

int n, m, a, b, c;
int ch[30];
priority_queue<Edge> pq;
vector<pair<int, int>> graph[30];
vector<int> dist;
void solve()
{
	cin >> n >> m;

	// 모든 정점까지의 거리는 매우 큰 숫자로 초기화
	dist = vector<int>(n + 1, 123456789);

	// 가중치 방향 그래프 생성
	for (int i = 1; i <= m; ++i)
	{
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
	}

	// 우선순위 큐 시작 정점 삽입
	pq.push({ 1,0 });
	dist[1] = 0; // 처음 시작은 거리가 0
	while (pq.empty() == false)
	{
		int cur = pq.top().v;
		int cost = pq.top().dist;
		pq.pop();

		// 이미 방문한 곳인데 더 작은 값이 존재한다면 스킵
		if (cost > dist[cur])
			continue;

		// 정점과 연결된 정점들 순회
		for (int i = 0; i < graph[cur].size(); ++i)
		{
			int next = graph[cur][i].first;
			int nextCost = cost + graph[cur][i].second; // 이전까지의 비용과 간선의 가중치의 합
			if (nextCost < dist[next]) // 찐또배기 작은 값
			{
				dist[next] = nextCost; // 거리값 갱신
				pq.push({ next, nextCost }); // 우선순위 큐에 삽입
			}
		}
	}
	
	for (int i = 2; i <= n; ++i)
	{
		if (dist[i] == 123456789)
			cout << i << " : " << "impossible" << '\n';
		else
			cout << i << " : " << dist[i] << '\n';
	}
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고