백준 11779번 - 최소비용 구하기 2

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

다익스트라를 활용한 문제이다.

 

문제 분석

 

기본적인 다익스트라 문제이다.

 

버스 비용이 다르다 -> 가중치가 다르다, 즉 다익스트라!

 

도시를 노드로, 버스 비용을 간선으로 바꾸어 그래프 문제로 모델링하면 된다.

 

 

이 문제의 특이한 점은 출력 조건이였다.

 

 

1. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용 출력

2. 경로에 포함되어있는 도시의 개수

3. 도시 순서대로 출력

 

 

최소 비용을 출력하는 것은... 당연한 얘기이다.

 

그럼 경로에 포함되어있는 도시의 개수는 어떻게 구해야 할까?

 

이것도 사실 bfs 문제를 많이 풀어보았으면 바로 감이 왔을 것이다.

바로 최소 비용으로 갱신될 때 이전 노드까지 거쳐온 도시의 개수 + 1을 해주면 된다.

 

도시 순서대로 출력 역시 마찬가지로

최소 비용으로 갱신될 때 이전 노드를 저장해놓는 배열을 따로 만들어 놓으면 된다.

 

코드는 다음과 같다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
vector<pair<int, int>>g[1004];
bool check[1004];
int dis[1004];
int ans[1004][2]; // [0] = 이전 노드 [1] = 몇 개의 도시를 거쳐왔는지
 
int main() {
    int n, m, start, end, u, v, e;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> e;
        g[u].push_back(make_pair(v, e));
    }
    cin >> start >> end;
    memset(dis, 127, sizeof(dis));
    dis[start] = 0;
    ans[start][0] = 0, ans[start][1] = 1; // 출발, 도착 도시도 포함
    priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int ver = pq.top().second;
        int wei = pq.top().first;
        pq.pop();
        if (check[ver] == true)continue;
        check[ver] = true;
        if (dis[ver] != wei) continue;
        for (int i = 0; i < g[ver].size(); i++) {
            int next = g[ver][i].first;
            int www = g[ver][i].second;
            if (dis[ver] + www < dis[next]) {
                dis[next] = dis[ver] + www;
                ans[next][0] = ver; // 이전 노드 (즉 어디서 왔는지, 세 번째 출력 조건)
                ans[next][1] = ans[ver][1] + 1; // 몇 번째로 왔는지(두 번째 출력 조건)
                pq.push(make_pair(dis[next], next));
            }
        }
    }
    cout << dis[end] << "\n";
    cout << ans[end][1] << "\n";
    int temp = end;
    vector<int>way;
    while (1) {
        way.push_back(temp);
        if (temp == start) break;
        temp = ans[temp][0];
    }
    for (int i = way.size() - 1; i >= 0; i--) cout << way[i] << " ";
    cout << "\n";
}

 

다른 사람들은 어떻게 해결했는지 잘 모르겠지만 아마 비슷하지 않을까 싶다..