結果

問題 No.2604 Initial Motion
ユーザー srjywrdnprktsrjywrdnprkt
提出日時 2024-01-14 23:47:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 681 ms / 3,000 ms
コード長 3,225 bytes
コンパイル時間 2,235 ms
コンパイル使用メモリ 223,608 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-29 10:38:48
合計ジャッジ時間 14,576 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 19 ms
5,248 KB
testcase_04 AC 19 ms
5,248 KB
testcase_05 AC 18 ms
5,248 KB
testcase_06 AC 18 ms
5,248 KB
testcase_07 AC 19 ms
5,248 KB
testcase_08 AC 18 ms
5,248 KB
testcase_09 AC 18 ms
5,248 KB
testcase_10 AC 18 ms
5,248 KB
testcase_11 AC 19 ms
5,248 KB
testcase_12 AC 18 ms
5,248 KB
testcase_13 AC 522 ms
5,248 KB
testcase_14 AC 296 ms
5,248 KB
testcase_15 AC 216 ms
5,248 KB
testcase_16 AC 452 ms
5,248 KB
testcase_17 AC 681 ms
5,248 KB
testcase_18 AC 627 ms
5,248 KB
testcase_19 AC 616 ms
5,248 KB
testcase_20 AC 437 ms
5,248 KB
testcase_21 AC 319 ms
5,248 KB
testcase_22 AC 593 ms
6,816 KB
testcase_23 AC 348 ms
6,820 KB
testcase_24 AC 496 ms
6,816 KB
testcase_25 AC 634 ms
6,820 KB
testcase_26 AC 409 ms
6,816 KB
testcase_27 AC 241 ms
6,820 KB
testcase_28 AC 368 ms
6,820 KB
testcase_29 AC 515 ms
6,816 KB
testcase_30 AC 275 ms
6,820 KB
testcase_31 AC 402 ms
6,816 KB
testcase_32 AC 383 ms
6,820 KB
testcase_33 AC 3 ms
6,820 KB
testcase_34 AC 374 ms
6,820 KB
testcase_35 AC 370 ms
6,816 KB
testcase_36 AC 357 ms
6,820 KB
testcase_37 AC 3 ms
6,816 KB
testcase_38 AC 2 ms
6,816 KB
testcase_39 AC 2 ms
6,816 KB
testcase_40 AC 258 ms
6,816 KB
testcase_41 AC 258 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>;

struct edge{
    int to; ll cap, cost; int rev;
};

struct MinCostFlow{

    private:
        static const ll INF=9e18;
        vector<ll> dist, h;
        vector<int> prevv, preve;
        vector<pair<int, int>> idx;

        void dijkstra(int s){
            int from, c;
            pq<pair<ll, int>> que;

            for (int i=0; i<N; i++) dist[i] = INF;
            que.push({0, s});
            dist[s] = 0;
            while(!que.empty()){
                tie(c, from) = que.top(); que.pop();
                if (dist[from] < c) continue;
                for (int i=0; i<E[from].size(); i++){
                    edge &e = E[from][i];
                    if (e.cap > 0 && dist[e.to] > dist[from]+e.cost+h[from]-h[e.to]){
                        dist[e.to] = dist[from]+e.cost+h[from]-h[e.to];
                        prevv[e.to] = from; preve[e.to] = i;
                        que.push({dist[e.to], e.to});
                    }
                }
            }
        }

    public:
        int N, M=0;
        vector<vector<edge>> E;

        MinCostFlow(int n) : N(n) {
            E.resize(N);
            dist.resize(N); h.resize(N);
            prevv.resize(N); preve.resize(N);
        }

        void add_edge(int from, int to, ll cap, ll cost){
            M++;
            idx.push_back({from, (int)E[from].size()});
            E[from].push_back({to, cap, cost, (int)E[to].size()});
            E[to].push_back({from, 0, -cost, (int)E[from].size()-1});
        }

        ll solve(int s, int t, ll f){
            ll res = 0, flow;
            fill(h.begin(), h.end(), 0);
            while(f){
                dijkstra(s);
                if (dist[t] == INF) return -1; //no solution

                for (int i=0; i<N; i++) h[i] += dist[i];
                flow = f;
                for (int i=t; i!=s; i=prevv[i]) flow = min(flow, E[prevv[i]][preve[i]].cap);
                f -= flow;
                res += flow*h[t];
                for (int i=t; i!=s; i=prevv[i]){
                    edge &e = E[prevv[i]][preve[i]];
                    e.cap -= flow;
                    E[i][e.rev].cap += flow;
                }
            }
            return res;
        }

        //i番目の辺の(from, to, flow)を求める。
        tuple<int, int, ll> get_flow(int i){
            assert (i < M);
            edge &e = E[idx[i].first][idx[i].second];
            return {idx[i].first, e.to, E[e.to][e.rev].cap};
        }
};

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    ll K, N, M, u, v, d, s, t;
    cin >> K >> N >> M;
    MinCostFlow mcf(N+2);
    s = 0;
    t = N+1;
    vector<ll> A(N+1), B(N+1);
    for (int i=1; i<=K; i++){
        cin >> u;
        A[u]++;
    }
    for (int i=1; i<=N; i++) cin >> B[i];
    for (int i=1; i<=N; i++) mcf.add_edge(s, i, A[i], 0);
    for (int i=1; i<=N; i++) mcf.add_edge(i, t, B[i], 0);

    for (int i=0; i<M; i++){
        cin >> u >> v >> d;
        mcf.add_edge(u, v, K, d);
        mcf.add_edge(v, u, K, d);
    }

    cout << mcf.solve(s, t, K) << endl;

    return 0;
}
0