提出 #46842071

---

ソースコード 拡げる

#include <bits/stdc++.h>

using Num = long long int;
Num n {0};
constexpr Num Size {1009};
Num mat[Size][Size];
constexpr Num INF = 1000000000000000000LL;

std::vector<Num> dijkstra_algo(Num start, Num scale, Num ofs) {
    std::vector<Num> distances(n, INF);
    using Node = std::pair<Num, Num>;
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> q;
    distances.at(start) = 0;
    q.push(std::make_pair(0, start));

    while(!q.empty()) {
        const auto [distance, from] = q.top();
        q.pop();

        if (distances.at(from) < distance) {
            continue;
        }

        for(decltype(n) to{0}; to<n; ++to) {
            if (from == to) {
                continue;
            }

            auto to_dist = (start == 0) ? mat[from][to] : mat[to][from];
            to_dist = to_dist * scale + ofs;
            to_dist += distance;
            if (to_dist < distances.at(to)) {
                distances.at(to) = to_dist;
                q.push(std::make_pair(to_dist, to));
            }
        }
    }

    return distances;
}

void solve(std::istream& is, std::ostream& os) {
    Num a {0};
    Num b {0};
    Num c {0};
    is >> n >> a >> b >> c;

    for(Num i{0}; i<n; ++i) {
        for(Num j{0}; j<n; ++j) {
            Num d {0};
            is >> d;
            mat[i][j] = d;
        }
    }

    const auto car_distances = dijkstra_algo(0, a, 0);
    const auto train_distances = dijkstra_algo(n - 1, b, c);

    Num answer {INF};
    for(Num i{0}; i<n; ++i) {
        answer = std::min(answer, car_distances.at(i) + train_distances.at(i));
    }

    os << answer << "\n";
    return;
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

提出情報

ジャッジ結果