[C++] 13804번 Road Construction - 데이크스트라, 그리디

13804번 Road Construction

 

1. 문제

• ACM 왕국의 왕 Mercer가 있다. 그 왕국에는 하나의 수도와 여러 개의 도시로 이루어져 있다. 원래 짜인 도로 건설 계획이 있었으나 비용 절감을 위해 다음과 같은 규칙을 적용하여 도로를 건설하는데 드는 비용을 최소화하려고 한다.
  • 모든 도시는 서로 갈 수 있는 길이 있어야 한다.
  • 도시에서 수도로 가는 최단 거리는 처음 계획과 달라지지 않는다.

<입력>

• -1- 도시의 개수 \(N(1 \leq N \leq 10,000)\), 도로의 개수 \(M(0 \leq M \leq 20,000)\)
• -M- 연결된 두 도시 u_i, v_i, 도로의 거리 d_i, 도로 건설비 c_i \((1 \leq u_i, v_i \leq N, u_i \leq v_i, 1 \leq d_i \leq 1,000, 1 \leq c_i \leq 1,000)\)

<출력>

• 도로를 건설하는데 드는 최소 비용을 출력하시오.

 

2. 재정의

• 무방향 연결 그래프가 주어졌을 때 1번 노드와 다른 노드 사이의 최단거리가 변하지 않는 선에서 간선을 제거하여 간선 생성 비용을 최소화하시오.

3. 해결 방법

1. 다익스트라로 각 노드까지의 최단거리를 계산함
2. 최단거리가 제일 높은 노드부터 차례대로 아래를 수행함
   1. 노드와 연결되어 있는 간선 중 최단거리가 되는 간선들 중 비용이 제일 작은 애만 남겨두고 나머지는 다 삭제
3. 간선의 건설 총비용을 구함

 

4. 실수한 점, 개선할 점

• 그리드 알고리즘에 너무 얽매여서 생각했었던 것 같다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 10001;
const int INF = 987654321;

struct Edge {
    int u, v, d, c;
} typedef Edge;

int N, M;
vector<vector<Edge>> graph(MAX_N);
vector<int> dist(MAX_N);
vector<int> Rank;
vector<bool> flag(MAX_N);
int res;

void input() {
    fill(dist.begin(), dist.end(), INF);
    fill(flag.begin(), flag.end(), false);
    for(int i=0; i<MAX_N; i++)
        graph[i].clear();
    Rank.clear();
    res = 0;
    
    for(int i=1; i<=N; i++)
        Rank.push_back(i);
    for(int i=0; i<M; i++) {
        int u, v, d, c;
        cin >> u >> v >> d >> c;
        Edge edge1 = {u, v, d, c};
        Edge edge2 = {v, u, d, c};
        graph[u].push_back(edge1);
        graph[v].push_back(edge2);
    
        res += c;
    }
}

void dijkstra() {
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    
    while(!q.empty()) {
        int parent = q.front(); q.pop();
        for(auto edge : graph[parent]) {
            if(dist[parent] + edge.d < dist[edge.v]) {
                dist[edge.v] = dist[parent] + edge.d;
                q.push(edge.v);
            }
        }
    }
}

bool compare(int a, int b) {
    return dist[a] > dist[b];
}

void solve() {
    dijkstra();
    
    sort(Rank.begin(), Rank.end(), compare);
    for(auto node : Rank) {
        if(node == 1)
            break;
        int Dist = dist[node];
        int cost_sum = 0;
        int min_cost = INF;
        for(auto y : graph[node]) {
            if(flag[y.v])
                continue;
            if(y.d + dist[y.v] == dist[node])
                min_cost = min(min_cost, y.c);
            cost_sum += y.c;
        } cost_sum -= min_cost;
        res -= cost_sum;
        flag[node] = true;
    }
    
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    while(1) {
        cin >> N >> M;
        if(!N && !M)
            break;
        
        input();
        
        solve();
    }
    
    return 0;
}

 

 

<문제 바로가기>

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

13804번: Road Construction