【AtCoder】ABC 362 D - Shortest Path 3 | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 634

問題概要

頂点 辺の単純連結無向グラフが与えられる。頂点 は の重みを持ち、辺 は頂点 に接続しており重み を持つ。このとき、各 について、頂点 から 頂点 までのパスであって、パス上に現れる頂点の重みと辺の重みの総和が最小となるものの値を求めよ。

制約

• 入力はすべて整数。
• 
• 
• 
• 

考察

頂点 を始点とする単一始点最短路問題ということで、このような問題は Dijkstra 法を用いて解を得ることができる。

一つ注意したいのは、本問では辺だけではなく頂点にも重みが付加されているということだ。一般的な Dijkstra 法のアルゴリズムでは辺にしか重みを付加できない。

そこで、辺の重みに頂点の重みを足し合わせてしまおう。具体的には、頂点 を結ぶ辺 について、 方向については重みを 、 方向については重みを とする。

このようなグラフ上で Dijkstra 法を適用し、最後に の重みを加えることで答えを求められる。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr auto INFL = 1LL << 60;

using ll = long long;
template <class T>
using Graph = vector<vector<T>>;


template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

using Pair_edge = std::pair<long long, int>;

struct Edge
{
    int to;
    long long cost;
};

// Solve the shortest path problem from the start point in the graph.
void Dijkstra(const Graph<Edge> &graph, std::vector<long long> &dist, const int start)
{
    std::priority_queue<Pair_edge, std::vector<Pair_edge>, std::greater<Pair_edge>> que;
    que.emplace((dist[start] = 0), start);

    while (!que.empty())
    {
        const long long distance = que.top().first;
        const int from = que.top().second;
        que.pop();

        if (dist[from] < distance)
            continue;

        for (const auto &edge : graph[from])
        {
            if (chmin(dist[edge.to], dist[from] + edge.cost))
            {
                que.emplace(dist[edge.to], edge.to);
            }
        }
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    rep(i, 0, N) cin >> A[i];
    Graph<Edge> G(N);
    rep(i, 0, M)
    {
        int U, V;
        cin >> U >> V;
        ll B;
        cin >> B;
        G[U - 1].push_back({V - 1, B + A[V - 1]});
        G[V - 1].push_back({U - 1, B + A[U - 1]});
    }

    vector<ll> dist(N, INFL);
    Dijkstra(G, dist, 0);

    rep(i, 1, N)
    {
        cout << A[0] + dist[i] << " ";
    }
    cout << endl;
}

atcoder.jp

実装時間: 20分

Dijkstra 法の実装に一工夫加えるという、とても教育的な問題だと思う。