반응형

www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=1;i<=n;i++)
#define pii pair<int, int>
#define MAX 200000000
using namespace std;
int n, e, a, b, c, v1, v2, ans1, ans2, dist[801];
struct cmp {
    bool operator()(const pii& a, const pii& b) {
        return a.second > b.second;
    }
};
vector<vector<pii> > vec;
priority_queue<pii, vector<pii>, cmp> pq;
void dijk(int start) {
    fill(dist, dist + n + 1, MAX);
    pq.push({ start, 0 });
    dist[start] = 0;
    while (!pq.empty()) {
        int now_v = pq.top().first;
        int now_w = pq.top().second;
        pq.pop();
        if (dist[now_v] < now_w) continue;
        for (pii next : vec[now_v]) {
            int next_v = next.first;
            int next_w = next.second + now_w;
            if (dist[next_v] > next_w) {
                dist[next_v] = next_w;
                pq.push({ next_v, next_w });
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> e;
    vec.resize(n + 1);
    rep(i, e) {
        cin >> a >> b >> c;
        vec[a].push_back({ b,c });
        vec[b].push_back({ a,c });
    }
    cin >> v1 >> v2;
    bool poss1 = true, poss2 = true;
    dijk(1);
    ans1 += dist[v1];
    ans2 += dist[v2];
 
    dijk(v1);
    ans1 += dist[v2];
    ans2 += dist[n];
 
    dijk(v2);
    ans1 += dist[n];
    ans2 += dist[v1];
    int ans = min(ans1, ans2);
    cout << (ans >= MAX ? -1 : ans);
        
}
cs
반응형

'백준 > 다익스트라' 카테고리의 다른 글

백준 1238 [복습 필수]  (0) 2021.02.19
백준 1261 [복습 필수]  (0) 2021.02.19
백준 1753 [복습 필수]  (0) 2021.02.19
반응형

www.acmicpc.net/problem/1238

 

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define MAX 987654321
#define pii pair<int, int>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, m, x, ans, dist[1001], sum[1001];
struct cmp {
    bool operator()(const pii& a, const pii& b) {
        return a.second > b.second;
    }
};
vector<vector<pii> > vec;
priority_queue<pii, vector<pii>, cmp> pq;
void dijk(int start) {
    fill(dist, dist + n + 1, MAX);
    pq.push({ start,0 });
    dist[start] = 0;
    while (!pq.empty()) {
        int now_v = pq.top().first;
        int now_w = pq.top().second;
        pq.pop();
 
        for (pii next : vec[now_v]) {
            int next_v = next.first;
            int next_w = next.second + now_w;
 
            if (dist[next_v] > next_w) {
                dist[next_v] = next_w;
                pq.push({ next_v, next_w });
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> x;
    vec.resize(n + 1);
    rep(i, m) {
        int a, b, w;
        cin >> a >> b >> w;
        vec[a].push_back({ b,w });
    }
 
    // 1. i -> x (찾아가기: n번)
    rep(i, n) {
        if (i == x) continue;
        dijk(i);
        sum[i] += dist[x];    // i에서 x까지 최단거리
    }
 
    // 2. x -> i (돌아오기: 1번)
    dijk(x);
    rep(i, n)
        sum[i] += dist[i];    // x에서 i까지 최단거리
 
    rep(i, n)
        ans = max(ans, sum[i]);
    cout << ans;
}
 cs

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define MAX 987654321
#define pii pair<int, int>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, m, x, ans, dist[1001], sum[1001];
struct cmp {
    bool operator()(const pii& a, const pii& b) {
        return a.second > b.second;
    }
};
vector<vector<pii> > vec;
vector<vector<pii> > vec_rev;
vector<vector<pii> > vec_copy;
priority_queue<pii, vector<pii>, cmp> pq;
void dijk(int start, int direction) {
    fill(dist, dist + n + 1, MAX);
    pq.push({ start,0 });
    dist[start] = 0;
    while (!pq.empty()) {
        int now_v = pq.top().first;
        int now_w = pq.top().second;
        pq.pop();
 
        if (direction)            // direction = 0 -> i에서 x로 찾아가기
            vec_copy = vec;        // direction = 1 -> x에서 i로 돌아가기
        else
            vec_copy = vec_rev;
 
        for (pii next : vec_copy[now_v]) {
            int next_v = next.first;
            int next_w = next.second + now_w;
 
            if (dist[next_v] > next_w) {
                dist[next_v] = next_w;
                pq.push({ next_v, next_w });
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> x;
    vec.resize(n + 1);
    vec_rev.resize(n + 1);
    rep(i, m) {
        int a, b, w;
        cin >> a >> b >> w;
        vec[a].push_back({ b,w });
        vec_rev[b].push_back({ a,w });
    }
 
    // 1. i -> x (찾아가기: 출발점 n개 도착점 1개를
    //                       출발점 1개 도착점 n개로 변경)
    dijk(x, 0);
    rep(i, n)
        sum[i] += dist[i];
 
    // 2. x -> i (돌아가기: 출발점 1개 도착점 n개)
    dijk(x, 1);
    rep(i, n)
        sum[i] += dist[i];
 
 
    rep(i, n)
        ans = max(ans, sum[i]);
    cout << ans;
}
 cs
반응형

'백준 > 다익스트라' 카테고리의 다른 글

백준 1504  (0) 2021.02.21
백준 1261 [복습 필수]  (0) 2021.02.19
백준 1753 [복습 필수]  (0) 2021.02.19
반응형

www.acmicpc.net/problem/1261

 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미

www.acmicpc.net

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
// https://chanhuiseok.github.io/posts/baek-17/
#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int, int>
#define rep(i,n) for(int i=1;i<=n;i++)
#define MAX 987654321
using namespace std;
int n, m, arr[101][101], dist[101][101];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
queue<pii> q;
void bfs() {
    q.push({ 1, 1 });
    dist[1][1] = 0;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx > 0 && nx <= m && ny > 0 && ny <= n) {
                // 1. 1 (벽)
                if (arr[nx][ny] == 1) {
                    if (dist[x][y] + 1 < dist[nx][ny]) {    // (현재 위치에서 다음 위치로 이동하는 비용) vs (이전에 찾아놓은 다음 위치로 이동하는 비용)
                        dist[nx][ny] = dist[x][y] + 1;
                        q.push({ nx, ny });
                    }
                }
                // 2. 0 (통로)
                else {
                    if (dist[x][y] < dist[nx][ny]) {        // (현재 위치에서 다음 위치로 이동하는 비용) vs (이전에 찾아놓은 다음 위치로 이동하는 비용)
                        dist[nx][ny] = dist[x][y];
                        q.push({ nx, ny });
                    }
                }
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    rep(i, m) {
        rep(j, n) {
            char c;
            cin >> c;
            arr[i][j] = c - '0';
            dist[i][j] = MAX;
        }
    }
    bfs();
    cout << dist[m][n];
}
 cs
반응형

'백준 > 다익스트라' 카테고리의 다른 글

백준 1504  (0) 2021.02.21
백준 1238 [복습 필수]  (0) 2021.02.19
백준 1753 [복습 필수]  (0) 2021.02.19
반응형

www.acmicpc.net/problem/1753

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.

www.acmicpc.net

 

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
#include <iostream>
#include <vector>
#include <queue>
#define rep(i,n) for(int i = 1; i<=n;i++)
#define pii pair<int, int>
#define MAX 987654321
using namespace std;
struct cmp {
    bool operator()(const pii& a, const pii& b) {
        return a.second > b.second;
    }
};
vector<vector<pii> > vec;                    // 그래프 저장용
priority_queue<pii, vector<pii>, cmp> pq;    // 간선 저장용 (가중치 오름차순 정렬)
int v, e, k, a, b, w, dist[20001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> v >> e >> k;
    vec.resize(v + 1);
 
    // 그래프 저장
    rep(i, e) {
        cin >> a >> b >> w;
        vec[a].push_back({ b, w });
    }
 
    // 거리 (or 비용 or 가중치) 초기화
    rep(i, v)
        dist[i] = MAX;
        
    // 시작점
    pq.push({ k, 0 });
    dist[k] = 0;
    while (!pq.empty()) {
        int now_v = pq.top().first;
        int now_w = pq.top().second;
        pq.pop();
 
        // 이미 최단 경로를 찾았으면 넘어가기
        //if (dist[now_v] < now_w) continue;
 
        // 연결된 정점 탐색
        for (auto i : vec[now_v]) {
            int next_v = i.first;
            int next_w = i.second + now_w;
            if (dist[next_v] > next_w) {        // 이전에 찾아놨던 next로 가는 비용 vs 현재 위치에서 next로 가는 비용
                pq.push({ next_v, next_w });
                dist[next_v] = next_w;            // 최단 거리 갱신
            }
        }
    }
    // 출력
    rep(i, v) {
        if (dist[i] == MAX)
            cout << "INF\n";
        else
            cout << dist[i] << '\n';
    }
}
 
 cs
반응형

'백준 > 다익스트라' 카테고리의 다른 글

백준 1504  (0) 2021.02.21
백준 1238 [복습 필수]  (0) 2021.02.19
백준 1261 [복습 필수]  (0) 2021.02.19

+ Recent posts

티스토리툴바