結果

問題 No.3111 Toll Optimization
ユーザー Tatsu_mr
提出日時 2025-04-19 11:31:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 253 ms / 5,000 ms
コード長 5,938 bytes
コンパイル時間 4,791 ms
コンパイル使用メモリ 289,852 KB
実行使用メモリ 88,664 KB
最終ジャッジ日時 2025-04-19 11:31:42
合計ジャッジ時間 13,486 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
#define SZ(v) ((int)(v).size())

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

struct SetupIo {
    SetupIo() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} setupio;

template <class T>
struct Edge {
    int from, to;
    T cost;
    int idx;
    
    Edge() {}
    Edge(int to_) : to(to_) {}
    Edge(int to_, T cost_) : to(to_), cost(cost_) {}
    Edge(int from_, int to_, int idx_) : from(from_), to(to_), idx(idx_) {}
    Edge(int from_, int to_, T cost_, int idx_) : from(from_), to(to_), cost(cost_), idx(idx_) {}
};

template <class T>
struct StaticGraph {
    private:
    template <class It>
    struct Es {
        It b, e;
        It begin() const { return b; }
        It end() const { return e; }
        int size() const { return int(e - b); }
        auto &&operator[](int i) const { return b[i]; }
    };
    
    int n;
    vector<pair<int, Edge<T>>> es;
    vector<int> start;
    vector<Edge<T>> eli;
    bool built;
    
    public:
    StaticGraph() {}
    StaticGraph(int n_) : n(n_), start(n + 1), built(false) {}
    
    void add(int u, int v) {
        assert(!built);
        assert(0 <= u && u < n); 
        assert(0 <= v && v < n);
        es.emplace_back(u, (Edge<T>){v});
    }
    
    void add(int u, int v, T w) {
        assert(!built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        es.emplace_back(u, (Edge<T>){v, w});
    }
    
    void add(int u, int u_, int v, int i) {
        assert(!built);
        assert(0 <= u && u < n);
        assert(u == u_);
        assert(0 <= v && v < n);
        es.emplace_back(u, (Edge<T>){u, v, i});
    }
    
    void add(int u, int u_, int v, T w, int i) {
        assert(!built);
        assert(0 <= u && u < n); 
        assert(0 <= v && v < n);
        assert(u == u_);
        es.emplace_back(u, (Edge<T>){u, v, w, i});
    }
    
    void build() {
        if (built) {
            return;
        }
        eli.resize(es.size());
        for (auto [v, e] : es) {
            start[v + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto [v, e] : es) {
            eli[counter[v]++] = e;
        }
        built = true;
    }
    
    int size() const { 
        return n; 
    }
    
    Es<typename vector<Edge<T>>::iterator> operator[](int v) {
        assert(built);
        assert(0 <= v && v < n);
        return {eli.begin() + start[v], eli.begin() + start[v + 1]};
    }
};

namespace dijkstra {

template <class T>
vector<T> Dijkstra(StaticGraph<T> &g, int s) {
    T mx = (is_same<T, int>::value ? 2000000000 : 1000000000000000000);
    vector<T> d(g.size(), mx);
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
    d[s] = T(0);
    pq.emplace(d[s], s);
    while (!pq.empty()) {
        auto [c, v] = pq.top();
        pq.pop();
        if (d[v] < c) {
            continue;
        }
        for (auto &e : g[v]) {
            int nv = e.to;
            T nc = c + e.cost;
            if (d[nv] > nc) {
                d[nv] = nc;
                pq.emplace(d[nv], nv);
            }
        }
    }
    return d;
}

template <class T>
struct DijkstraRestore {
    private:
    int s;
    T mx;
    vector<T> d;
    vector<Edge<T>> prev;
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
    
    public:
    DijkstraRestore() {}
    DijkstraRestore(StaticGraph<T> &g, int s_) : s(s_), prev(g.size()) {
        mx = (is_same<T, int>::value ? 2000000000 : 1000000000000000000);
        d.resize(g.size(), mx);
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        d[s] = T(0);
        pq.emplace(d[s], s);
        while (!pq.empty()) {
            auto [c, v] = pq.top();
            pq.pop();
            if (d[v] < c) {
                continue;
            }
            for (auto &e : g[v]) {
                int nv = e.to;
                T nc = c + e.cost;
                if (d[nv] > nc) {
                    d[nv] = nc;
                    prev[nv] = e;
                    pq.emplace(d[nv], nv);
                }
            }
        }
    }
    
    vector<T> dists() const { 
        return d; 
    }
    
    T dist(int t) const {
        assert(0 <= t && t < (int)d.size());
        return d[t]; 
    }
    
    vector<Edge<T>> route(int t) const {
        assert(0 <= t && t < (int)d.size());
        if (s == t || d[t] == mx) {
            return {};
        }
        vector<Edge<T>> res;
        int cur = t;
        while (cur != s) {
            res.emplace_back(prev[cur]);
            cur = prev[cur].from;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

} // namespace dijkstra

using namespace dijkstra;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<lint> c(m);
    rep(i, m) {
        cin >> c[i];
    }
    StaticGraph<lint> g((k + 1) * n);
    rep(i, m) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        rep(j, k + 1) {
            int x = u + j * n;
            int y = v + j * n;
            g.add(x, y, c[i]);
            g.add(y, x, c[i]);
        }
        rep(j, k) {
            g.add(u + j * n, v + (j + 1) * n, 0LL);
            g.add(v + j * n, u + (j + 1) * n, 0LL);
        }
    }
    g.build();
    auto d = Dijkstra(g, 0);
    lint ans = LINF;
    rep(i, k + 1) {
        ans = min(ans, d[(n - 1) + i * n]);
    }
    cout << (ans != LINF ? ans : -1) << "\n";
}
0