BOJ 3526번 이상적인 경로

문제 링크

\(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 의 최단경로에 포함이 된다. 왜냐하면

....

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

#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] != -1) continue;
            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()==0) break;
        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;
}