반응형

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

 

11779번: 최소비용 구하기 2

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

일반적인 최소 거리를 구하는 다익스트라 문제였습니다. 하지만 거기에 경로를 출력하라는 요구사항이 있었기 때문에 조금 더 복잡했지만 몇 줄 추가만 해주면 쉽게 풀리는 문제였습니다.

 

Bus struct 안에 경로를 저장할 vector를 추가해 주었고, 이를 pq에 넣어주면 각 인자별로 경유지를 따로 저장할 수 있기 때문에 목적지에 도착했을 때 이 경유지를 따로 저장만 해주면 됩니다.

 

[ 소스 코드 ]

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct Bus {                    //노선의 정보를 저장할 struct
    int to;
    int cost;
    vector<int> via;
};
 
int n, m;
int visited[1001];            //방문 여부 체크
vector<Bus> list[1001];        //버스 도착지와 cost를 저장할 vector list
 
bool cmp(Bus left, Bus right)    //가격이 낮은 순으로 list를 정렬
{
    return left.cost < right.cost;
}
 
struct comp {                    //가격이 낮은 순으로 priority_queue에서 빠져나옴
    bool operator()(Bus right, Bus left)
    {
        return left.cost < right.cost;
    }
};
 
int main()
{
    int start, end;
    int ans;                //총 가격 저장할 변수
    vector<int> ansVia;        //경로를 저장할 vector
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {    //노선 정보를 list에 입력
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        list[start].push_back({ end,cost });
    }
 
    cin >> start >> end;
 
    for (int i = 1; i <= n; i++) {    //가격이 낮은 순으로 정렬
        sort(list[i].begin(), list[i].end(), cmp);
    }
 
    priority_queue<Bus, vector<Bus>, comp> pq;
    vector<int> via;
    pq.push({ start,0, via});        //시작점을 pq에 넣기
    
 
    while (!pq.empty())
    {
        int to = pq.top().to;
        int cost = pq.top().cost;
        vector<int> via = pq.top().via;
 
        pq.pop();
 
        if (visited[to] == 1) continue;    //방문했다면 continue
        visited[to]++;
        via.push_back(to);
 
        if (to == end) {        //목적지에 도착하면 비용과 경로를 저장
            ans = cost;
            ansVia = via;
            break;
        }
 
        for (int i = 0; i < list[to].size(); i++) {
            int next = list[to][i].to;
            int nextCost = list[to][i].cost;
            if (visited[next] != 1) {        //방문하지 않았다면
                pq.push({ next, cost + nextCost, via});    //다음 노드와 여기까지 오는데 드는 비용, 경로를 pq에 넣기
            }
        }
    }
 
    printf("%d\n%d\n", ans, ansVia.size());        //출력
    for (int i = 0; i < ansVia.size(); i++) {
        printf("%d ", ansVia[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01

+ Recent posts

티스토리툴바