백준 1753(최단경로)

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

1753번: 최단경로

 

엄청 단순한 다익스트라 문제. 

 

문제에서 요구하는 바가 무조건 다익스트라이다.

근데 고비가 있었다. 이제까지 인접행렬로 문제를 풀었었기 때문에 이 문제 또한 인접행렬로 문제를 풀려고 했지만, vertex가 20,000 이므로 만약에 인접행렬로 푼다면 20000*20000 4억 메모리제한에 걸리게 된다. 

 

따라서 인접리스트로 문제를 풀어야한다. 

 

인접리스트를 사용하려면 vector에 대해서 좀 알아야 하는데 

vector은 index접근도 가능하고, 뒤에 집어넣는 push_back함수도 있다. 

이것만 인지하고 있으면 나머지는 같다.

 

 

먼저 출발점에서 인접한 모든 점을 priority_queue에 집어넣는다. 

가장 작은 거리를 통해서 가는 나머지 거리들을 계산 후에 그 거리를 최신화 해준다. 

 

만약 dist(시작점 0)배열이 

 

0 2 1 4 5 9

 

이렇게 존재한다면 

 

여기서 가장 작은 거리인 1 index = 2를 거쳐서 가는 경우와 그렇지 않은 경우를 비교, 만약에 더 적게 걸린다면 그 거리로 최신화 해주고 그 경우를 pq에 집어넣는다. 

 

pq가 빌때까지 반복한다.

 

#include<iostream>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
#define MAX 20001
#define MAX2 300001

priority_queue<pair<int, int> > pq;
pair<int, int> p;
vector<pair<int, int> > adj[MAX];
int dist[MAX];
int V, E, start, INF = 987654321, a, b, c;
bool checked[MAX] = { false };

void solve() {
	for (int i = 0; i < adj[start].size(); i++) {
		pq.push(make_pair(-adj[start][i].second, adj[start][i].first));
	}
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (!checked[p.second]) {
			checked[p.second] = true;
			for (int i = 0; i < adj[p.second].size(); i++) {
				if (dist[adj[p.second][i].first] > dist[p.second] + adj[p.second][i].second) {
					dist[adj[p.second][i].first] = dist[p.second] + adj[p.second][i].second;
					pq.push(make_pair(-dist[adj[p.second][i].first], adj[p.second][i].first));
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> V >> E >> start;
	for (int i = 0; i < E;  i++) {
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		if (a == start) {
			if(dist[b] == 0 || dist[b] > c)
				dist[b] = c;
		}
	}
	for (int i = 1; i <= V; i++) {
		if (start != i && dist[i] == 0) dist[i] = INF;
	}
	


	solve();

	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}

}

 

 

주의점

 

이 문제에서는 a->b로 가는 경로가 하나가 아니다. 따라서 그것을 확인해주어야 한다. 

받은 입력중에 최단 경로만 저장한다.