일단 최소비용 문제니까 다익스트라, 벨만포드 / 플로이드 워셜을 떠올릴 수가 있고
여기서 한 출발점에 대한 최단거리만 구하면 되니까 다익스트라나 벨만포드를 쓰면 되겠다고 생각할 수 있고
마지막으로 간선의 가중치가 모두 양의 값이기 때문에 다익스트라를 쓰면 되겠다고 생각할 수 있다.

이걸 알았으니 이제 그래프 구현하고 다익스트라 짜서 원하는 출발점의 모든 간선에 대한 최단거리를 구한 다음에 원하는 도착점의 값을 출력하기만 하면 끝!

처음 짠 코드는 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;
const int INF = 987654321;

vector<vector<pi>> graph;
vector<int> dist;
int start, arrive;

void solve() {
    priority_queue<pi> pq;
    dist[start] = 0;
    //가중치, 노드
    pq.push({dist[start], start});

    while (!pq.empty()) {
        pi top = pq.top();
        int v = top.second;
        pq.pop();
        for (pi node : graph[top.second]) {
            if (dist[v] + node.first < dist[node.second]) dist[node.second] = dist[v] + node.first;
            pq.push({dist[node.second], node.second});
        }
    }

}

int main() {
    int n, m;
    cin >> n >> m;
    graph.assign(n + 1, vector<pi>());
    dist.assign(n + 1, INF);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        //가중치, 노드
        graph[a].push_back({c, b});
    }
    cin >> start >> arrive;
    solve();
    cout << dist[arrive];
}

2퍼에서 바로 메모리 초과가 났다…ㅋ

로직에 문제는 없는 것 같아서 질문 게시판을 좀 뒤져보니까 2%에서 에러가 나면 인풋이 중복돼서 들어오는 테케도 있어서 그거 처리를 제대로 했는지 확인해보라는 답변이 있었다.

음… 꽤나 가능성 있어 보인다.

그래서 처음은 그래프를 인접 그래프로 구현했는데, 만약 같은 구간에 대한 값이 여러 번 들어오고 그 값 중 최솟값을 비교해야 하는 상황이면 인접 행렬로 구현해서 아예 칸을 만들어두는 게 더 나으니까… 그렇게 고치기로 했다. 이 문제는 애초에 노드 개수도 별로 안 많기도 하고

그래서 어찌저찌 고쳤다!

오늘도 언제나 내 곁에 두고 매번 챙겨보는 필독서… competitive programer’s handbook을 참고했다.
생각해보니까 c++ pq는 최대 힙이 디폴트인걸 깜빡하고 있었다. 가중치 음으로 바꿔줌ㅋㅋㅋㅋㅋ

그러고 나니 무난히 맞았다.

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;
const int INF = 987654321;

vector<vector<int>> graph;
vector<int> dist;
vector<bool> visited;

int n, m;
int start, arrive;

void solve() {
    priority_queue <pi> pq;

    dist[start] = 0;
    //가중치, 간선
    pq.push({dist[start], start});

    while (!pq.empty()) {
        pi top = pq.top();
        pq.pop();
        int v = top.second;
        if (visited[v]) continue;
        visited[v] = true;

        for (int i = 1; i <= n; i++) {
            if (graph[v][i] == INF) continue;
            dist[i] = min(dist[i], graph[v][i] + dist[v]);
            pq.push({-dist[i], i});
        }
    }

}

int main() {
    cin >> n >> m;
    graph.assign(n+1, vector<int> (n+1, INF));
    dist.assign(n+1, INF);
    visited.assign(n+1, false);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = min(graph[a][b], c);
    }
    cin >> start >> arrive;

    solve();

    cout << dist[arrive];
}

그래도 이번 학기에 자료구조 들으면서 다익스트라는 자유자재로 구현할 수 있을 만큼 이해했다고 생각했는데, 막상 코드 짜보니까 그것도 아닌 것 같다ㅋㅋㅋㅋㅋㅜㅜㅜ

아직도 갈 길이 두고두고 멀다는 것을 느낀다…