블로그 옮겼습니다

BOJ 3526번 이상적인 경로 본문

Algorithm/Problem Solving

BOJ 3526번 이상적인 경로

sgc109 2017. 5. 7. 16:35
문제 링크


\(2\leq{N}\leq{10^5}\)
\(1\leq{M}\leq{2\cdot{10^5}}\)
\(1\leq{c}\leq{10^9}\)

노드의 개수 N, 엣지의 개수 M, 각 엣지에는 색 c 가 부여된다. 색은 정수로 주어진다. 엣지는 양방향이다.
두 노드 사이에 엣지는 여러개 있을 수 있다.
출발점은 1번노드, 도착점은 N번노드이다. 출발점에서 도착점까지 갈 때 지나는 통로의 색을 순서대로 적는다.
출발점부터 도착점까지 최단경로로 갈 때의 색의 sequence 를 구하는 문제. 만약 최단경로가 여러개라면
사전순으로 앞서는 sequence 를 구하는 문제이다.

우선 priority_queue 를 사용해 다익스트라를 하듯이 거리와 색의 우선순위에 따라 도착지까지 가면서
색의 seqeunce 를 구해주면 될 거라고 생각했는데, 이 방법은 어떤 노드까지의 최단거리가 곧 도착지까지의
최단거리가 되지는 않으며, 그렇기 때문에 출발지 부터 거리가 k인 노드들에 대해 사전순만 보고 판단하면
안된다. 그럼 어떻게 할까?
일단 먼저 출발점에서 bfs로 각각의 노드까지의 최단거리를 구해준다. 이 정보를 dist 배열이 가지고있다고 하겠다.
그리고 도착점에서도 bfs로 각각의 노드까지의 최단거리도 구해준다. 이 정보는 ridst 배열이 가지고있다고 하겠다.

이걸 구해 놓으면 이 정보를 바탕으로 어떤 특정 엣지가 출발점->도착점의 최단경로에 포함이
되는 엣지인지 아닌지 O(1)에 판단을 할 수가 있다.
어떻게 하냐면 현재 노드 u에서 u->v 의 엣지를 보고있다고 해보자(출발점은 S, 도착점은 E)
그리고 S에서 u까지의 최단경로를 포함하는 S->E의 최단경로가 존재한다고 가정하자. 그러면
dist[v] + rdist[v] 가 dist[E] 와 같으면 u->v 은 S->E 의 최단경로에 포함이 된다. 왜냐하면

....
나중에 다시 공부해야겠다. 아직 완벽하게 이해를 못한듯 ㅠ



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
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int N,M;
vector<pair<int,int> > G[100003];
queue<int> q;
vector<int> ans;
vector<pair<int,int> > v;
set<int> st;
int dist[100003];
int rdist[100003];
int parent[100003];
void bfs(int S, int* d){
    while(!q.empty()) q.pop();
    q.push(S);
    d[S] = 0;
    while(!q.empty()){
        int here = q.front();
        q.pop();
        for(auto p : G[here]){
            int there = p.second;
            if(d[there] != -1continue;
            d[there] = d[here] + 1;
            q.push(there);
        }
    }
}
int main() {
    scanf("%d%d",&N,&M);
    memset(dist,-1,sizeof(dist));
    memset(rdist,-1,sizeof(rdist));
    for(int i = 0 ; i < 100003; i++) G[i].clear();
    
    ans.clear();
    v.clear();
    st.clear();
 
    for(int i = 0 ; i < M; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back({c,b});
        G[b].push_back({c,a});
    }
 
    bfs(1,dist);
    bfs(N,rdist);
 
    q.push(1);
    while(!q.empty()){
        if(q.front() == N) break;
        v.clear();
        while(!q.empty()) {
            int here = q.front();
            q.pop();
            for(auto p : G[here]) {
                int there = p.second;
                if(dist[here]+1 != dist[there] || dist[there] + rdist[there] != dist[N]) continue;
                v.push_back(p);
            }
        }
        if(v.size()==0break;
        sort(v.begin(), v.end());
        int col = v[0].first;
        ans.push_back(col);
        st.clear();
        for(int i = 0 ; i < v.size(); i++) {
            if(v[i].first > col) break;
            st.insert(v[i].second);
        }
        for(auto x : st) q.push(x);
    }
 
    printf("%d\n",ans.size());
    for(int i = 0 ; i < ans.size(); i++) {
        printf("%d ",ans[i]);
    }
    return 0;
}
 
cs


'Algorithm > Problem Solving' 카테고리의 다른 글

BOJ 9426번 중앙값 측정  (0) 2017.05.09
Topcoder SRM 714 Div1(Easy) Paranthesis Removal  (0) 2017.05.08
BOJ 3681번 모빌  (0) 2017.05.06
UVa OJ 12118 - Inspector's Dilemma  (0) 2017.05.06
UVa OJ 11898 - Killer Problem  (0) 2017.05.06
Comments