백준
백준 12763 지각하면 안 돼
콩순이냉장고
2021. 11. 12. 18:26
문제 URL : https://www.acmicpc.net/problem/12763
12763번: 지각하면 안 돼
1호관에서 3호관, 4호관을 거쳐 5호관으로 간다면, 3시간만에 3500원의 지출로 도착할 수 있다. (다행히 이번 수업은 휴강이었다고 합니다.)
www.acmicpc.net
문제 접근법 :
다양한 문제접근법이 있는데
dfs를이용해서 전수조사를 해도되고 다익스트라를 이용해서 탐색을 해도됩니다.
이번문제는 좀 쉬운문제를 어렵게 풀어보기위해
ㅋㅋㅋㅋ
다익스트라를 이용해봤습니다. 다익스트라를 이용하기위해선
모든비용에대해서도 최소거리를 판단해줘야합니다.
즉 dist를 2차원으로 생각하셔야합니다.
소스코드 :
|
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
|
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
v<tuple<int,int,int>> path[101];
int n,t,m,l;
void input() {
cin >> n;
cin >> t >> m;
cin >> l;
for (int i = 0; i < l; i++) {
int a, b, c,d;
cin >> a >> b >> c >> d;
path[a].push_back({ b,c,d });
path[b].push_back({ a,c,d });
}
}
struct point {
int cur,totaltime,sumcost;
friend bool operator<(const point& a, const point& b) {
return a.totaltime > b.totaltime;
}
};
int dijkstrak() {
vvi dist(n + 1, vi(m + 1, 1e8));
dist[1][0] = 0;
priority_queue<point> pq;
pq.push({ 1,0,0 });
while (!pq.empty()) {
int cur = pq.top().cur;
int sumcost = pq.top().sumcost;
int totaltime = pq.top().totaltime;
pq.pop();
if(dist[cur][sumcost]<totaltime)continue;
for (int i = 0; i < path[cur].size(); i++) {
int next, ntime, cost;
tie(next, ntime, cost) = path[cur][i];
ntime += totaltime;
cost += sumcost;
if (cost<=m&&dist[next][cost] > ntime) {
dist[next][cost] = ntime;
pq.push({ next,ntime,cost });
}
}
}
int res = 1e8;
for (int i = 0; i <= m; i++) {
if (dist[n][i] <= t)
return i;
}
return -1;
}
void solve() {
cout << dijkstrak() << "\n";
}
int main() {
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
return 0;
}
|
cs |
궁금한점 혹은 모르는점 혹은 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
공감 눌러주실꺼죠?