BOJ 1504 특정한 최단 경로

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/1504

🧐 관찰 및 접근
#

$a$에서 $b$까지 가되, $v_1, v_2$를 무조건 지니야 한다.
- 이는 $a \rightarrow v_1 \rightarrow v_2 \rightarrow b$ 혹은 $a \rightarrow v_2 \rightarrow v_1 \rightarrow b$ 두가지중 하나이지 않을까?
  - 각 움직임에 대해 나이브하게 다익스트라를 수행해도 6번밖에 안되므로, 그냥 돌리자.
경로가 없을 수 있음에 유의하자.

💻 풀이
#

코드 (C++):

int N, E;
vector<pii> links[810];

int get_dist(int s, int e){
    vector<int> dist(N+1, 1e9);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(dist[u] < d) continue;
        if(u == e) return d;
        for(auto [v, w]: links[u]){
            if(dist[v] > d+w){
                dist[v] = d+w;
                pq.push({dist[v], v});
            }
        }
    }
    return 1e8;
}

void solve(){
    cin >> N >> E;
    rep(i, 0, E){
        int u, v, w; cin >> u >> v >> w;
        links[u].push_back({v, w});
        links[v].push_back({u, w});
    }
    int v1, v2; cin >> v1 >> v2;
    int ans = min(get_dist(1, v1) + get_dist(v1, v2) + get_dist(v2, N), get_dist(1, v2) + get_dist(v2, v1) + get_dist(v1, N));
    if(ans >= 1e8) cout << -1;
    else cout << ans;
}

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#