結果

問題 No.3111 Toll Optimization
ユーザー hot-cocoa
提出日時 2025-04-19 02:17:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 288 ms / 5,000 ms
コード長 3,120 bytes
コンパイル時間 1,062 ms
コンパイル使用メモリ 91,068 KB
実行使用メモリ 19,636 KB
最終ジャッジ日時 2025-04-19 02:18:00
合計ジャッジ時間 12,420 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <limits>

using int64 = long long;
const int64 INF = 1e18;

template<class T>
class edge {
public:
    int to;
    T weight;

    edge(int to, T weight) : to{to}, weight{weight} {}
};

template<class T>
using Graph = std::vector<std::vector<edge<T>>>;

template<class T>
class Dijkstra {
private:
    Graph<T> g;
    const T INF = std::numeric_limits<T>::max() / 2;

    struct State {
        int v;
        T weight;

        State(int v, T weight) : v{v}, weight{weight} {}

        bool operator < (const State& s) const
        {
            return weight > s.weight;
        }
    };

public:
    Dijkstra(const Graph<T>& g) : g{g} {}

    std::vector<T> shortest_path(int s)
    {
        std::priority_queue<State> pq;
        pq.emplace(s, 0);

        std::vector<T> weight(g.size(), INF);
        weight[s] = 0;

        const auto& update = [&](const edge<T>& e, const State& s) -> bool
        {
            if (weight[s.v] + e.weight >= weight[e.to])
                return false;

            weight[e.to] = weight[s.v] + e.weight;
            return true;
        };

        while (!pq.empty()) {
            auto [v, w] = pq.top(); pq.pop();
            if (weight[v] < w)
                continue;

            for (const edge<T>& e : g[v])
                if (update(e, {v, w}))
                    pq.emplace(e.to, weight[e.to]);
        }

        return weight;
    }

    bool is_updated(T w)
    {
        return w != INF;
    }
};

int main()
{
    int N, M, K;
    std::cin >> N >> M >> K;
    
    Graph<int64> graph(N + 1);
    std::vector<int64> c(M);
    for (int i = 0; i < M; i++) {
        std::cin >> c[i];
    }
    for (int i = 0; i < M; i++) {
        int u, v;
        std::cin >> u >> v;
        u--; v--;
        graph[u].emplace_back(v, c[i]);
        graph[v].emplace_back(u, c[i]);
    }
    
    std::vector<std::vector<int64>> dist(N + 1, std::vector<int64>(K + 1, INF));
    dist[0][0] = 0;
    
    std::priority_queue<std::tuple<int64, int, int>, std::vector<std::tuple<int64, int, int>>, std::greater<>> pq;
    pq.push({0, 0, 0});
    
    while (!pq.empty()) {
        auto [cost, v, used_coupon] = pq.top();
        pq.pop();
        
        if (cost > dist[v][used_coupon]) continue;
        
        for (auto [next_v, edge_cost] : graph[v]) {
            if (dist[v][used_coupon] + edge_cost < dist[next_v][used_coupon]) {
                dist[next_v][used_coupon] = dist[v][used_coupon] + edge_cost;
                pq.push({dist[next_v][used_coupon], next_v, used_coupon});
            }
            
            if (used_coupon < K && dist[v][used_coupon] < dist[next_v][used_coupon + 1]) {
                dist[next_v][used_coupon+1] = dist[v][used_coupon];
                pq.push({dist[next_v][used_coupon + 1], next_v, used_coupon + 1});
            }
        }
    }
    
    int64 answer = INF;
    for (int k = 0; k <= K; k++) {
        answer = std::min(answer, dist[N - 1][k]);
    }
    
    std::cout << (answer == INF ? -1 : answer) << std::endl;
    
    return 0;
}
0