백준 16528번 Highway Decommission

문제 링크입니다: https://www.acmicpc.net/problem/16528

다익스트라(Dikjstra) 문제인데 조금 꼬아서 낸 문제였습니다.

전형적인 다익스트라 문제와 다르게 '고속도로 유지 비용'이라는 변수도 추가되었습니다.

알고리즘은 아래와 같습니다.

1. 고속도로 유지 비용이 추가되었기 때문에 pair<int, pair<int, int>> 대신 Edge 구조체를 정의해줍니다.

-> 우선순위 큐를 사용할 것이기 때문에 < 연산자도 정의해줍니다.

a) 거리가 가까울수록

b) 거리가 같다면 가격이 저렴할수록

c) 우선순위가 높습니다.

2. 전형적인 다익스트라 알고리즘을 진행합니다.

i) e.city에서 next.city로 가는 거리가 기존에 저장된 거리보다 가깝다면 거리를 업데이트하고 유지 비용도 업데이트해주고 우선순위 큐에 해당 정보를 넣어줍니다.

ii) e.city에서 next.city로 가는 거리가 같은데 유지 비용이 더 저렴하다면 유지 비용을 업데이트해주고 우선순위 큐에 해당 정보를 넣어줍니다.

3. 2번을 마치면 고속도로 유지 비용을 전부 더해준 뒤 출력해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <functional>

#include <cstring>

#include <climits>

using namespace std;

 

const int MAX = 10000;

 

typedef struct

{

        int city;

        long long len, cost;

}Edge;

 

bool operator<(const Edge &e1, const Edge &e2)

{

        if (e1.len > e2.len)

                 return true;

        //거리가 같을 경우 가격이 더 저렴한 쪽이 우선순위가 높다

        else if (e1.len == e2.len && e1.cost > e2.cost)

                 return true;

        return false;

}

 

int N, M;

vector<Edge> graph[MAX];

long long dist[MAX];

long long price[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int from, to;

                 long long dist, cost;

                 cin >> from >> to >> dist >> cost;

 

                 //양방향

                 graph[from - 1].push_back({ to - 1, dist, cost });

                 graph[to - 1].push_back({ from - 1, dist, cost });

        }

 

        priority_queue<Edge> pq;

        pq.push({ 0, 0, 0 }); //시작점에서는 dist, cost 모두 0

        dist[0] = 0; //시작점

        for (int i = 1; i < N; i++)

                 dist[i] = LLONG_MAX;

 

        while (!pq.empty())

        {

                 Edge e = pq.top();

                 pq.pop();

 

                 for (int i = 0; i < graph[e.city].size(); i++)

                 {

                         Edge next = graph[e.city][i];

                         //거리가 더 멀 경우

                         if (dist[next.city] > (dist[e.city] + next.len))

                         {

                                 dist[next.city] = dist[e.city] + next.len;

                                 price[next.city] = next.cost;

                                 pq.push({ next.city, dist[next.city], price[next.city] });

                         }

                         //거리는 같은데 더 비쌀 경우

                         else if (dist[next.city] == (dist[e.city] + next.len) && price[next.city] > next.cost)

                         {

                                 price[next.city] = next.cost;

                                 pq.push({ next.city, dist[next.city], price[next.city] });

                         }

                 }

        }

 

        long long result = 0;

        for (int i = 0; i < N; i++)

                 result += price[i];

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~