티스토리 뷰

알고리즘 관련/BOJ

BOJ)13911 집 구하기

JASON 자손9319 2016. 12. 30. 15:54

문제: icpc.me/13911


맥세권과 스세권을 만족하는 집 중 최단거리의 합이 최소인 집을 구하면 된다.


맥도날드로 부터 거리를 구하기 위한 다익스트라와 스타벅스로 부터 거리를 구하기 위한 다익스트라를 두번 돌려 준 후


mdp[x]와 sdp[x]가 정해진 거리를 만족하면서(맥세권,스세권이면서) mdp[x]+sdp[x]가 최소인 거리를 출력해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;
int v, e, a, b, c, mx, my, x, y, res;
vector<vector<pair<intint>>> vt;
vector<int> m;
vector<int> s;
int mdp[10010];
int sdp[10010];
int main()
{
    scanf("%d%d"&v, &e);
    vt.resize(v + 1);
    for (int i = 0; i < e; i++) {
        scanf("%d%d%d"&a, &b, &c);
        vt[a].push_back({ b,c });
        vt[b].push_back({ a,c });
    }
    scanf("%d%d"&mx, &x);
    for (int i = 0; i < mx; i++) {
        scanf("%d"&a);
        m.push_back(a);
    }
    scanf("%d%d"&my, &y);
    for (int i = 0; i < my; i++) {
        scanf("%d"&a);
        s.push_back(a);
    }
    memset(mdp, -1sizeof(mdp));
    memset(sdp, -1sizeof(sdp));
    priority_queue<pair<intint>> pq;
    for (int i = 0; i < mx; i++
        pq.push({ 0,m[i] });
    while (pq.size()) {
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        if (mdp[here] != -1)continue;
        mdp[here] = cost;
        for (int i = 0; i < vt[here].size(); i++) {
            if (mdp[vt[here][i].first] != -1)continue;
            pq.push({ -cost - vt[here][i].second,vt[here][i].first });
        }
    }
    priority_queue<pair<intint>> spq;
    for (int i = 0; i < my; i++
        spq.push({ 0,s[i] });
    while (spq.size()) {
        int here = spq.top().second;
        int cost = -spq.top().first;
        spq.pop();
        if (sdp[here] != -1)continue;
        sdp[here] = cost;
        for (int i = 0; i < vt[here].size(); i++) {
            if (sdp[vt[here][i].first] != -1)continue;
            spq.push({ -cost - vt[here][i].second,vt[here][i].first });
        }
    }
    res = INF;
    for (int i = 1; i <= v; i++) {
        if (mdp[i] == -1 || sdp[i] == -1)
            continue;
        if (mdp[i] != 0 && sdp[i] != 0 && mdp[i] <= x&&sdp[i] <= y) {
            res = min(res, mdp[i] + sdp[i]);
        }
    }
    if (res == INF)
        printf("-1");
    else
        printf("%d", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11895 속이기  (0) 2017.01.03
BOJ)2401 최대 문자열 붙여넣기  (1) 2016.12.30
BOJ)13168 내일로 여행  (0) 2016.12.30
BOJ)13911 집 구하기  (0) 2016.12.30
BOJ 5719) 거의 최단 경로  (12) 2016.12.29
BOJ 7894) 큰 숫자  (0) 2016.12.29
댓글
댓글쓰기 폼