백준 1735 (최단경로) c++

문제

1753번: 최단경로

v개의 정점과 e개의 간선정보를 입력받습니다.

간선정보는 {a, b, c}로 이루어져 있는데 a로부터 b로 가는 경로가 있는데 c만큼 비용이 든다 라는 의미입니다.

시작점을 입력받을 때 시작점에서 시작해서 1번 정점부터 v번 정점까지 최단 경로 비용을 각각 구하는 문제입니다.

또한 각 정점과 정점은 여러개의 경로가 있을 수 있습니다.

 

일단 처음에 이 문제를 봤을 때 정점과 정점 사이의 비용이 음수가 없어서 다익스트라 알고리즘을 생각해보기도

했습니다. 하지만 정점과 정점 사이의 여러개의 경로가 있다는 점, 그리고 방향성이 있는 그래프라는 점에서

다익스트라가 아닌줄 알았습니다.

 

방향성이 없다보니 시작점을 기준으로 dfs 를 통해 시작점으로 부터 도달 할 수 있는 정점의 비용들을

갱신해 주었습니다. 

하지만 "메모리 초과" 를 받았습니다.

 

다시 찾아보니 다익스트라 문제였습니다.

사실 방향성이 있다 없다는 크게 문제 되지 않았습니다.

하지만 정점과 정점 사이에 간선이 여러개가 존재한다는 점에서 저는 다익스트라를 생각하지 못했습니다.

아마 저 스스로 다익스트라 알고리즘을 제대로 이해하지 못한것 같습니다...

 

간선이 비용이 작은것 부터 다익스트라 알고리즘을 적용하게 '우선 순위 큐'를 사용해 

간선과 간선 사이이 비용을 갱신해주고 

더 큰 비용이 들면 그냥 무시해주면 됩니다.

 

int d[20001];
vector<pair<int, int>>adj[20001];

int v, e;
cin >> v >> e;
int start;
cin >> start;

for (int i = 0; i < e; i++) {
	int a, b, c;
	cin >> a >> b >> c;
	adj[a].push_back({ b, c });
}
fill(d, d + 20001, MAX);

 먼저 입력 부분입니다.

평소 처럼 정점의 정보를 벡터에 넣어 줍니다.

d 배열은 start(시작점) 으로 부터 드는 비용을 저장하는 배열입니다.

priority_queue<pair<int, int>>pq;
pq.push({ 0,start });
d[start] = 0;
while (!pq.empty()) {
	int cost = -pq.top().first;
	int vertex = pq.top().second;
	pq.pop();
	for (auto nxt : adj[vertex]) {
		int next = nxt.first;
		int ncost = nxt.second;
		if (d[next] > d[vertex] + ncost) {
			d[next] = d[vertex] + ncost;
			pq.push({ -d[next], next });
		}
	}
}

우리가 평소하는 다익스트라와 똑같습니다.

 

괜히 쫄아서 그렇지 기본적인 다익스트라 알고리즘입니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int d[20001];
vector<pair<int, int>>adj[20001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    
    int v, e;
    cin >> v >> e;
    int start;
    cin >> start;
 
    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ b, c });
    }
    fill(d, d + 20001, MAX);
 
    priority_queue<pair<int, int>>pq;
    pq.push({ 0,start });
    d[start] = 0;
    while (!pq.empty()) {
        int cost = -pq.top().first;
        int vertex = pq.top().second;
        pq.pop();
        for (auto nxt : adj[vertex]) {
            int next = nxt.first;
            int ncost = nxt.second;
            if (d[next] > d[vertex] + ncost) {
                d[next] = d[vertex] + ncost;
                pq.push({ -d[next], next });
            }
        }
    }
 
    for (int i = 1; i <= v; i++) {
        if (d[i] == MAX)cout << "INF" << '\n';
        else cout << d[i]<<'\n';
    }
    return 0;
}