반응형
https://www.acmicpc.net/problem/20183
20183번: 골목 대장 호석 - 효율성 2
첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의
www.acmicpc.net
[ 문제풀이 ]
1. 그래프를 입력받고, vector<pair<int, int>> list[ 100001 ] 배열에 저장합니다.
2. 매개 변수를 활용하여 이동할 수 있는 골목의 최대 비용을 정해서 dijkstra를 돌립니다.
3. ans를 -1로 초기화하고, 만약 도착지에 도착하게 되면 ans에 해당 매개 변수 값을 저장합니다.
4. ans를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<queue> #include<vector> #define ll long long using namespace std; int N, M; int A, B; ll C; vector<pair<int, int>> list[100001]; int s, e; int ans = -1; ll visited[100001]; bool dijkstra(int m) { fill(visited, visited + N + 1, 111111111111111); priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq; pq.push({ 0,A }); while (!pq.empty()) { const ll cost = pq.top().first; const int cur = pq.top().second; pq.pop(); if (cost > C) continue; if (cur == B) { return true; } if (visited[cur] < cost) continue; visited[cur] = cost; for (auto& next : list[cur]) { if (visited[next.second] > cost + next.first && next.first <= m) { visited[next.second] = cost + next.first; pq.push({ cost + next.first, next.second }); } } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M >> A >> B >> C; s = 1; for (int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; list[u].push_back({ w,v }); list[v].push_back({ w,u }); e = max(e, w); } while (s <= e) { int m = (s + e) / 2; if (dijkstra(m)) { ans = m; e = m - 1; } else { s = m + 1; } } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 5569번 - 출근 경로 (C++) (0) | 2023.09.18 |
---|---|
[ 백준 ] 13398번 - 연속합 2 (C++) (0) | 2023.09.17 |
[ 백준 ] 5549번 - 행성 탐사 (C++) (0) | 2023.09.15 |
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++) (0) | 2023.09.14 |
[ 백준 ] 9084번 - 동전 (C++) (0) | 2023.09.13 |