반응형

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

 

24042번: 횡단보도

당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받으면서 몇 분에 어떤 횡단보도를 건널 수 있는지 list에 저장합니다.

 

2. 데이크스트라를 이용하여 1번 지역부터 돌면서 다음에 갈 수 있는 지역의 신호가 파란불로 바뀌는 시점이 현재 시점보다 앞이면 거리 ndist = cnt + M - cnt % M + next.second + 1, 뒤라면 ndist = cnt - cnt % M + next.second + 1로 설정하여 pq에 넣어줍니다.

 

3. 현재 지역이 N지역이라면 cnt를 출력해줍니다.

 

[ 소스코드 ]

 

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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
struct node {
    int cur;
    ll cnt;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.cnt < right.cnt;
    }
};
 
int N, M;
ll visited[100001];
vector<pair<int, ll>> list[700001];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        visited[i] = 1844674407370955161;
    }
 
    for (ll i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].emplace_back(b, i);
        list[b].emplace_back(a, i);
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ 1,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().cur;
        const ll cnt = pq.top().cnt;
        pq.pop();
 
        if (cur == N) {
            printf("%lld", cnt);
            return 0;
        }
 
        for (const auto& next : list[cur]) {
            if ((cnt % M) - 1 > next.second) {    //현재보다 앞의 상태
                ll ndist = cnt + M - cnt % M + next.second + 1;
                if (visited[next.first] > ndist) {
                    visited[next.first] = ndist;
                    pq.push({ next.first, ndist });
                }
            }
            else if ((cnt % M) - 1 < next.second) {    //현재보다 뒤의 상태
                ll ndist = cnt - cnt % M + next.second + 1;
                if (visited[next.first] > ndist) {
                    visited[next.first] = ndist;
                    pq.push({ next.first, ndist });
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09
[ 백준 ] 16393번 - Lost Map (C++)  (0) 2022.12.08
[ 백준 ] 1016번 - 제곱 ㄴㄴ 수 (C++)  (0) 2022.12.07

+ Recent posts

티스토리툴바