How We Coding

[1162] 도로포장

BOJ/Shortest Path2018. 7. 28. 00:47

### Dijkstra ###


[1162] 도로포장 : http://boj.kr/1162


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
const int INF = 1e9;
 
typedef pair<int, int> P;
typedef pair<int, P> K;
 
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
 
    vector<P> g[10001];
    while(m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back(P(b, c));
        g[b].push_back(P(a, c));
    }
 
    vector<vector<int> > dist(k+1, vector<int>(n+1, INF)); 
    dist[k][1] = 0; // kth pave, cur vertex
 
    priority_queue<K> pq;
    pq.push(K(0, P(1, k))); // dist, v, k
 
    bool visited[21][10001]={0}; 
  
    while(!pq.empty()) {
        int curV, curK;
        do {
            curV = pq.top().second.first;
            curK = pq.top().second.second; 
            pq.pop();
        } while(!pq.empty() && visited[curK][curV]);
  
        if(visited[curK][curV]) break;
        visited[curK][curV] = 1;
 
        for(auto &p : g[curV]) {
            int nextV = p.first;
            int d = p.second;
            
            if(dist[curK][nextV] > dist[curK][curV] + d) {
                dist[curK][nextV] = dist[curK][curV] + d;
                pq.push(K(-dist[curK][nextV], P(nextV, curK)));
            }
            if(curK-1 >= 0 && dist[curK-1][nextV] > dist[curK][curV]) {
                dist[curK-1][nextV] = dist[curK][curV];
                pq.push(K(-dist[curK-1][nextV], P(nextV, curK-1)));
            }
        }
    }
    
    int ans = 1e9;
    for(int i=0; i<=k; i++) {
        ans = min(ans, dist[i][n]);
    }
    
    printf("%d\n", ans);
    return 0;
}
 
cs

>> dist[k][i] : 포장을 k개 할 수 있는 상태에서 시작정점에서 i번 정점까지의 최단거리, 

    k값의 변화가 없는 겨우, 우리가 지금까지 구했던 다익스트라 dist 배열이다.


'BOJ > Shortest Path' 카테고리의 다른 글

[5917] 거의 최단경로  (0) 2018.07.26
[13424] 비밀 모임  (0) 2018.07.24
[10282] 해킹  (0) 2018.07.24

[5917] 거의 최단경로

BOJ/Shortest Path2018. 7. 26. 00:03

### Dijkstra ###


[5917] 거의 최단경로 : http://boj.kr/5917


<소스코드>


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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, s, e;
const int INF=1e9;
typedef pair<int, int> P;
 
vector<int> from[501];
 
void remove(vector<int> *from, int path[][501], int next)
{
    if(next == s) return ; 
 
    for(int i=0; i<from[next].size(); i++) {
        int cur = from[next][i];
        path[cur][next] = INF;
        remove(from, path, cur);
    }
 
}
 
int dijkstra(vector<P> *g, int path[][501])
{
    priority_queue<P> pq;
    pq.push(P(0, s));
 
    vector<int> dist(n+1, INF);
    dist[s] = 0;
 
    vector<bool> visited(n+1, 0);
 
    while(!pq.empty()) {
        int cur;
        do {
            cur = pq.top().second;
            pq.pop();
        } while(!pq.empty() && visited[cur]);
 
        if(visited[cur]) break;
 
        visited[cur] = 1;
 
        for(auto &p : g[cur]) {
            int next = p.first;
            int d = path[cur][next];
 
            if(dist[cur] + d == dist[next]) {
                from[next].push_back(cur);
            }
            else if(dist[next] > dist[cur] + d) {
                dist[next] = dist[cur] + d;
                pq.push(P(-dist[next], next));
                from[next].clear();
                from[next].push_back(cur);
            }
        }
    }
 
    return dist[e];    
}
 
int main()
{
    while(1) {
        scanf("%d%d", &n, &m);
        if(n == 0 && m == 0) break;
 
        scanf("%d%d", &s, &e);
 
        vector<P> g[501];
        int path[501][501]={0};
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(P(b, c));
            path[a][b] = c;
        }
 
        for(int i=0; i<n; i++)
            from[i].clear();
       
        int ans = dijkstra(g, path);
        if(ans == INF) {
            puts("-1");
            continue;
        }
        remove(from, path, e);
           
        ans = dijkstra(g, path);
        if(ans == INF) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}
 
cs

>> 푸는데 참 오래 걸렸다.

>> 결론적으로 다익스트라 두번 돌렸으며, 처음 돌릴때, from 벡터배열에 한 정점까지의 최단경로에 대한 이전 정점들에 대해 기록을 해두고,

>> remove 로 삭제. 그리고 다시 다익스트라를 한번 돌리면 된다. 


>> 주의할 것이 두가지 있었다. 처음 다익스트라를 돌렸을때 처음부터 갈수 없는 경로가 존재하는 경우에 대해 처리하는 것과

>> 다음으론 k 번 정점까지의 최단거리로 오는 방법이 한가지 가 아닌경우, 그 모든 경우에 대한 간선을 제거하는 것.!!


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
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
5 3
0 4
0 1 1
0 2 1
0 3 1
5 6
0 4
0 1 10
0 2 1
2 1 2
1 3 1
3 4 2
1 4 5
6 8 
0 5
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0 2 2
2 5 10
0 5 5
0 0
 
cs


위 테스트 케이스에 대해 아래와 같이 정답이 나와야 한다.

마지막 테스트 케이스가 12가 나오면 여러가지 길이 있을 때, 한가지 길만 제거해서 생긴거라고 생각하면 된다.


5

-1

6

-1

15

-1

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[13424] 비밀 모임  (0) 2018.07.24
[10282] 해킹  (0) 2018.07.24

[13424] 비밀 모임

BOJ/Shortest Path2018. 7. 24. 16:29

### Dijkstra or Floyd ###


[13424] 비밀 모임 : http://boj.kr/13424



<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
const int INF=1e9;
typedef pair<int, int> P;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, m;
        scanf("%d%d", &n, &m);
 
        vector<P> g[101];
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(P(b, c));
            g[b].push_back(P(a, c));
        }
        
        int k, f;
        scanf("%d", &k);
        
        vector<int> ans(n+1, 0);
        for(int i=0; i<k; i++) {
            scanf("%d", &f);
            vector<bool> visited(n+1);
            vector<int> dist(n+1, INF);
            dist[f] = 0;
 
            priority_queue<P> pq;
            pq.push(P(0, f));
 
            while(!pq.empty()) {
                int cur;
                do {
                    cur = pq.top().second;
                    pq.pop();
                } while(!pq.empty() && visited[cur]);
 
                if(visited[cur]) break;
                visited[cur] = 1;
 
                for(auto &p : g[cur]) {
                    int next = p.first;
                    int d = p.second;
                    if(dist[next] > dist[cur] + d) {
                        dist[next] = dist[cur] + d;
                        pq.push(P(-dist[next], next));
                    }
                }
            }
            for(int i=0; i<=n; i++) {
                ans[i] += dist[i]; 
            }
        }
 
        int idx=1, minD=INF; 
        for(int i=1; i<=n; i++) {
            if(minD > ans[i]) {
                minD = ans[i];
                idx = i;
            }
        }
        printf("%d\n", idx);
    }
}
 
 
cs


>> 더 빠른시간에 수행된 다른사람들의 코드를 보니 플로이드로 풀었다.

>> n 제한이 100이라 플로이드로 돌려도 된다고 생각했지만, 다익스트라 공부중이라 다익스트라로 품

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[5917] 거의 최단경로  (0) 2018.07.26
[10282] 해킹  (0) 2018.07.24

[10282] 해킹

BOJ/Shortest Path2018. 7. 24. 15:22

### Dijkstra ###


[10282] 해킹 : http://boj.kr/10282


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long int lli;
const lli INF = 1e15;
typedef pair<int, int> P;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, d, c;
        scanf("%d%d%d", &n, &d, &c);
 
        vector<P> g[10001];
        for(int i=0; i<d; i++) {
            int a, b, s;
            scanf("%d%d%d", &a, &b, &s);
            // a 가 b를 의존
            // b 가 감염되면 s초 후에 a도 감염.
            g[b].push_back(P(a, s));
        }
    
        priority_queue<P> pq;
        pq.push(P(0, c)); 
 
        vector<bool> visited(n+1);
        vector<lli> dist(n+1, INF);
        dist[c] = 0;
 
        while(!pq.empty()) {
            int cur;
            do {
                cur = pq.top().second;
                pq.pop();
            } while(!pq.empty() && visited[cur]);
 
            if(visited[cur]) break;
            visited[cur] = 1;
            
            for(auto &p : g[cur]) {
                int next = p.first;
                int d = p.second;
                if(dist[next] > dist[cur] + d) {
                    dist[next] = dist[cur] + d;
                    pq.push(P(-dist[next], next));
                }
            }
        }
 
        int cnt=0, time=0;
        for(int i=1; i<=n; i++) {
            if(dist[i] != INF) {
                cnt++;
                if(time < dist[i])
                    time = dist[i];
            }
        }
        printf("%d %d\n", cnt, time);
    }
    return 0;
}
 
 
cs

>> 

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[5917] 거의 최단경로  (0) 2018.07.26
[13424] 비밀 모임  (0) 2018.07.24

티스토리툴바