반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 다익스트라 알고리즘


이 문제는 다익스트라를 이용하여 최단 거리의 경로 추적까지 모든 것을 요구하고 있다.


다익스트라를 배운 코더라면 한번쯤 복습해볼만한 좋은 문제인 것 같다.


추적하는 방법은 아래 trace[next] = here; 만 추가해주면 추적을 할 수 있게 된다.


다음번째 경로의 배열에 이전 위치를 계속 저장하게 되면 역추적이 가능하게 되기 때문이다.






소스 코드 : 


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
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <memory.h>
#include <stack>
 
#define INF 987654321
 
using namespace std;
 
typedef pair<int, int> pii;
 
vector<pii> vc[1001];
int trace[1001];
 
int main()
{
    int V, E;
    scanf("%d %d", &V, &E);
 
    memset(trace, -1, sizeof(trace));
    for (int i = 0; i < E; i++)
    {
        int from, to, val;
        scanf("%d %d %d", &from, &to, &val);
 
        vc[from].push_back(pii(to, val));
   
    }
        
    int s, e;
    scanf("%d %d", &s, &e);
 
    int dist[1001];
    fill(dist, dist + 1001, INF);
    
    dist[s] = 0;
 
    priority_queue<pii, vector<pii>, greater<pii>> pq;
 
    pq.push({ 0,s });
 
 
    while (!pq.empty())
    {
        int here = pq.top().second;
        int hereCost = pq.top().first;
 
        pq.pop();
 
        if (dist[here] < hereCost)
            continue;
 
        for (int i = 0; i < vc[here].size(); i++)
        {
            int next = vc[here][i].first;
            int nextCost = vc[here][i].second + hereCost;
 
            if (dist[next] > nextCost)
            {
                dist[next] = nextCost;
 
                trace[next] = here;
                pq.push({ nextCost, next });
            }
        }
    }
 
    cout << dist[e] << endl;
    int cnt = 1;
    for (int i = e; i != s; i = trace[i])
        cnt++;
 
    cout << cnt << endl;
 
    stack<int> st;
    for (int i = e; i != s; i = trace[i])
        st.push(i);
    st.push(s);
    
    while (!st.empty())
    {
        printf("%d ", st.top());
        st.pop();
    }
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2414번] 게시판 구멍 막기  (0) 2017.04.12
[1867번] 돌멩이 제거  (0) 2017.04.12
[1420번] 학교 가지마!  (0) 2017.04.11
[1733번] 등번호  (0) 2017.04.10
[7616번] 교실로 가는 길  (0) 2017.04.09

티스토리툴바