1719번

1719번 - 택배

오랜만에 다익스트라를 쓰려고 하니 많이 헷갈렸다. 이 문제는 다익스트라 + 경로 추적이라고 생각.

각 정점마다 다익스트라를 실행하고, p 배열을 이용해서 부모 노드를 저장한다.

최소값을 모두 구하고, 부모노드를 이용해서 처음 방문하는 값들을 구했다.

(처음 방문하는 값들의 부모가 시작 노드라는 점을 이용)

####  

이 문제를 거의 이틀이나 잡고 있었다. 계속 puts 를 쓰고 있었기 때문이었다... 하 별거 아닌 거로 너무 시간을 쏟았다..

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
const int INF = 987654321;
int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, m;
    cin >> n >> m;
 
    vector<vector<pair<int, int>>> node(n + 1);
 
    while (m--)
    {
        int from, to, w;
        cin >> from >> to >> w;
        node[from].push_back({ to,w });
        node[to].push_back({ from,w });
    }
 
    // i 번 정점부터 다익스트라.
    for (int i = 1; i <= n; i++)
    {
        vector<int> dist(n + 1, INF);
        vector<int> p(n + 1, -1);
        priority_queue<pair<int, int>> q;
        dist[i] = 0;
        q.push({ -dist[i],i });
 
        while (!q.empty())
        {
            int cost = -q.top().first;
            int here = q.top().second;
            q.pop();
 
            if (dist[here] < cost)
            {
                continue;
            }
 
            for (int d = 0; d < node[here].size(); d++)
            {
                int there = node[here][d].first;
                int w = node[here][d].second;
 
                if (dist[there] > cost + w)
                {
                    p[there] = here;
                    dist[there] = cost + w;
                    q.push({ -dist[there],there });
                }
            }
        }
 
        for (int k = 1; k <= n; k++) {
            int t = k;
            if (i == t)
            {
                cout << "- ";
            }
            else
            {
                while (p[t] != i) {
                    t = p[t];
                }
                cout << t << " ";
            }
        }
        cout << endl;
    }
 
    return 0;
}