[BOJ] 1719 택배

문제

1719번: 택배

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다.

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

풀이

코드

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
 
int n, m;
vector<pii> v[200];
pii dis[200];
int ans[200][200];
 
void go(int s) {
    for(int i = 0; i < n; i++) {
        dis[i].first = 1e9;
        dis[i].second = -1;
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, s});
    dis[s].first = 0;
 
    while (!pq.empty()) {
        int d = pq.top().first, now = pq.top().second; pq.pop();
        if (d > dis[now].first) continue;
        for(pii i : v[now]) {
            if (dis[i.first].first <= i.second + dis[now].first) continue;
            dis[i.first].first = i.second + dis[now].first;
            dis[i.first].second = now;
            pq.push({dis[i.first].first, i.first});
        }
    }
    for(int i = s; i < n; i++) ans[i][s] = dis[i].second;
    for(int i = s; i >= 0; i--) ans[i][s] = dis[i].second;
}
 
int main() {
    scanf("%d %d", &n, &m);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    for(int i = 0; i < n; i++) go(i);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if (i == j) printf("- ");
            else printf("%d ", ans[i][j]+1);
        }
        printf("\n");
    }
}