백준 5901번 Relocation

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

다익스트라 알고리즘을 이용해 푸는 문제였습니다.

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

1. 장터가 있는 마을을 입력받고, 해당 마을에 장터가 있다고 표시합니다.

2. 양방향 그래프를 입력받고 각각의 마을에 대해 다익스트라 알고리즘을 통해 최단경로를 계산합니다.

3. 어디에 거주를 할지 모르기 때문에 모든 경우의 수를 파악합니다.

i) next_permutation을 이용하여 K! 순열을 확인합니다.

ii) 처음과 끝은 해당 거주지로부터 출발하므로 양 끝 경로도 더해서 계산해야합니다.

iii) ii) 중 최소의 값이 정답입니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <functional>

#include <cstring>

#include <queue>

using namespace std;

 

const int MAX = 10000 + 1;

const int INF = 987654321;

 

int N, K, M;

int market[5];

bool isMarket[MAX];

int path[5][MAX];

bool visited[MAX];

vector<pair<int, int>> graph[MAX];

 

//전형적인 다익스트라

void dijkstra(int start)

{

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

        {

                 path[start][i] = INF;

                 visited[i] = false;

        }

 

        priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        pq.push({ 0, market[start] });

        path[start][market[start]] = 0;

 

        while (!pq.empty())

        {

                 int cost = pq.top().first;

                 int node = pq.top().second;

                 pq.pop();

 

                 if (visited[node])

                         continue;

 

                 visited[node] = true;

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

                 {

                         int nextCost = graph[node][i].first + cost;

                         int nextNode = graph[node][i].second;

 

                         if (nextCost < path[start][nextNode])

                         {

                                 path[start][nextNode] = nextCost;

                                 pq.push({ nextCost, nextNode });

                         }

                 }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M >> K;

 

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

        {

                 cin >> market[i];

 

                 market[i] -= 1;

                 isMarket[market[i]] = true;

        }

 

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

        {

                 int src, dest, cost;

                 cin >> src >> dest >> cost;

 

                 src -= 1;

                 dest -= 1;

                 //양방향

                 graph[src].push_back({ cost, dest });

                 graph[dest].push_back({ cost, src });

        }

 

        //최단 경로 파악

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

                 dijkstra(i);

 

        int result = INF;

        int order[5] = { 0, 1, 2, 3, 4 };

        do

        {

                 int cost = 0;

                 //마켓을 순회하는 경로를 계산

                 for (int i = 0; i < K - 1; i++)

                         cost += path[order[i]][market[order[i + 1]]];

 

                 //시작과 끝을 더해주고 비교

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

                         if (!isMarket[i])

                                 result = min(result, cost + path[order[0]][i] + path[order[K - 1]][i]);

        } while (next_permutation(order, order + K));

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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