#53833: cpp answer


yp11451151@yphs.tp.edu.tw (701-30郭宸碩)

學校 : 臺北市私立延平高級中學
編號 : 312874
來源 : [203.72.178.1]
最後登入時間 :
2025-10-02 17:58:06

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e15;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a, b, x, y;
    if (!(cin >> a >> b >> x >> y)) return 0;
    
    // 節點編號:A_i -> i (1..100), B_i -> i+100 (101..200)
    int N = 200;
    vector<vector<pair<int,int>>> adj(N+1);
    
    // Ai <-> Bi (同樓層通道)
    for (int i = 1; i <= 100; ++i) {
        int u = i;
        int v = i + 100;
        adj[u].push_back({v, x});
        adj[v].push_back({u, x});
    }
    // Ai+1 <-> Bi (斜通道) for i = 1..99  => connect A(i+1) with B(i)
    for (int i = 1; i <= 99; ++i) {
        int u = (i+1);      // A_{i+1}
        int v = i + 100;    // B_i
        adj[u].push_back({v, x});
        adj[v].push_back({u, x});
    }
    // Ai <-> Ai+1 (A樓樓梯) and Bi <-> Bi+1 (B樓樓梯)
    for (int i = 1; i <= 99; ++i) {
        int a1 = i, a2 = i+1;
        adj[a1].push_back({a2, y});
        adj[a2].push_back({a1, y});
        int b1 = i+100, b2 = i+1+100;
        adj[b1].push_back({b2, y});
        adj[b2].push_back({b1, y});
    }
    
    int start = a;         // A_a
    int target = b + 100;  // B_b
    
    // Dijkstra
    vector<ll> dist(N+1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d,u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        if (u == target) break;
        for (auto &e : adj[u]) {
            int v = e.first;
            ll w = e.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    cout << dist[target] << "\n";
    return 0;
}