dp, dijkstra 둘 다 가능하다. 속도는 32MS, 4MS로 다익스트라가 더 빠르다.


dp를 사용할 때 도로의 통행료가 0일 수 있어서 ans로 일단 구하고 d[x][y]에 넣는 방법으로 하면 무한루프에 빠져 런타임 에러가 난다.


일단 INF를 넣어주고 최소값을 구하면 무한루프를 피할 수 있다.


<dp code>

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
#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
struct rd {
    int y, l, t;
    rd(int y=0, int l=0, int t=0) : y(y), l(l), t(t) {}
};
 
int k, n, r, d[101][10001];
vector<rd> v[101];
 
int dp(int x, int y) {
    if (d[x][y] != -1) return d[x][y];
    if (x == n) return 0;
    d[x][y] = 2e9;
    for (auto i : v[x]) {
        if (y - i.t < 0) continue;
        d[x][y] = min(d[x][y], dp(i.y, y - i.t) + i.l);
    }
    return d[x][y];
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d%d", &k, &n, &r);
    while (r--) {
        int s, e, l, t;
        scanf("%d%d%d%d", &s, &e, &l, &t);
        v[s].push_back({ e,l,t });
    }
    int ans = dp(1, k);
    printf("%d\n", ans == 2e9 ? -1 : ans);
    return 0;
}
cs



<dijkstra code>

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
#include <stdio.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct rd {
    int y, l, t;
    rd(int y=0, int l=0, int t=0) : y(y), l(l), t(t) {}
};
 
int k, n, r, d[101][10001];
vector<rd> v[101];
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d%d", &k, &n, &r);
    while (r--) {
        int s, e, l, t;
        scanf("%d%d%d%d", &s, &e, &l, &t);
        v[s].push_back({ e,l,t });
    }
    priority_queue <pair<int, pair<int, int>>> q;
    q.push({ 0,{0,1} });
    while (q.size()) {
        int x = q.top().second.second, c = -q.top().first, t = -q.top().second.first;
        if (x == n) {
            printf("%d", c);
            return 0;
        }
        q.pop();
        if (d[x][t] != -1) continue;
        d[x][t] = c;
        for (auto i : v[x]) {
            if (t + i.t > k || d[i.y][t + i.t] != -1) continue;
            q.push({ -c - i.l,{-t - i.t,i.y} });
        }
    }
    printf("-1");
    return 0;
}
cs


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

'BOJ' 카테고리의 다른 글

3372 보드 점프  (0) 2017.08.31
11762 A Towering Problem  (0) 2017.08.31
10025 게으른 백곰  (0) 2017.08.30
14619 섬 여행  (0) 2017.08.30
11664 선분과 점  (0) 2017.08.30

+ Recent posts

티스토리툴바