티스토리 뷰

알고리즘 관련/BOJ

BOJ)2211 네트워크 복구

JASON 자손9319 2017. 1. 26. 16:14

문제:icpc.me/2211


원본 네트워크가 주어질 때 1.최소 개수의 회선만 복구하면서 2. 1번 노드에서 k번 노드의 최단거리가 원본보다 길어지지 않도록 복구하라는 문제이다.


처음에 1번 조건만 봤을때는 MST를 떠올릴 수 있으나 2번조건 때문에 다익스트라를 이용하여 1번 정점부터 최단거리를 구해주면서 사용되는 모든 간선을 벡터에 저장해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define MAX_N 1000
using namespace std;
int n, m, a, b, c, dp[MAX_N + 1];
priority_queue<pair<int, pair<intint>>> pq;
vector<pair<intint>> res;
vector<vector<pair<intint>>> vt;
int main() {
    scanf("%d%d"&n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d"&a, &b, &c);
        vt[a].push_back({ b,c });
        vt[b].push_back({ a,c });
    }
    memset(dp, -1sizeof(dp));
    pq.push({ 0,{1,0} });
    while (pq.size()) {
        int here = pq.top().second.first;
        int cost = -pq.top().first;
        int par = pq.top().second.second;
        pq.pop();
        if (dp[here] != -1)continue;
        dp[here] = cost;
        if (par)
            res.push_back({ here,par });
        for (auto next:vt[here]) {
            int there = next.first;
            if (dp[there] != -1)continue;
            pq.push({ -cost - next.second, {there,here} });
        }
    }
    printf("%d\n", res.size());
    for (auto x : res)
        printf("%d %d\n", x.first, x.second);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)3682 동치 증명  (0) 2017.01.31
BOJ)11338 XOR Sum  (0) 2017.01.31
BOJ)2211 네트워크 복구  (0) 2017.01.26
BOJ)2275 트리의 높이 줄이기  (0) 2017.01.25
BOJ)8012 한동이는 영업사원!  (2) 2017.01.25
BOJ)1761 정점들의 거리  (0) 2017.01.25
댓글
댓글쓰기 폼