Baekjoon1753-최단경로

백준 사이트 1753 - 최단경로 문제입니다.

1. 문제

https://www.acmicpc.net/problem/1753

---

2. Input , Output

---

3. 분류 및 난이도

그래프 다익스트라 문제입니다.
백준에서는 Gold5난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 다익스트라에 익숙하지 않아 겁내했던 문제입니다.
• 그 덕에 멘탈이 박살났습니다. 많이 틀렸고 많이 고쳤습니다.
• 가중치를 먼저 꺼내야한다는 것이 포인트입니다. 가중치를 기준으로 꺼내는게 맞으니까요.

---

5. code

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int INF = 987654321;
const int MAX = 20010;
int V,E;
int current;
vector<pair<int, int>> v[MAX];
int di[MAX];

void Input()
{
	int start, end, weight;
	
	
	cin >> V >> E;
	cin >> current;
	for (int i = 0; i < E; ++i)
	{
		cin >> start >> end >> weight;
		v[start].push_back(make_pair(end, weight));
	}
	for (int i = 1; i <= V; ++i)
		di[i] = INF;

}

void dijkstra(int start)
{
	di[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0,start));

	while (!pq.empty())
	{
		int distance = -pq.top().first;
		int curr = pq.top().second;
		pq.pop();
		for (int i = 0; i < v[curr].size(); ++i)
		{
			int next = v[curr][i].first;
			int nextDistance = v[curr][i].second+distance;
			if (nextDistance < di[next])
			{
				di[next] = nextDistance;
				pq.push(make_pair(-nextDistance,next));
			}
		}

	}
}

void Solve()
{
	//다익스트라
	dijkstra(current);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	Solve();
	for (int i = 1; i <= V; ++i)
	{
		if (di[i] != INF)
			cout << di[i] << '\n';
		else
			cout << "INF\n";
	}
	return 0;
}

---

6. 후기

이거풀고 너무 힘들어서 집감…