結果

問題 No.2915 辺更新価値最大化
ユーザー SnowBeenDidingSnowBeenDiding
提出日時 2024-10-04 22:56:36
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 1,703 bytes
コンパイル時間 5,175 ms
コンパイル使用メモリ 310,156 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-04 22:56:43
合計ジャッジ時間 5,567 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 AC 10 ms
6,820 KB
testcase_08 AC 12 ms
6,816 KB
testcase_09 AC 14 ms
6,820 KB
testcase_10 AC 15 ms
6,820 KB
testcase_11 AC 14 ms
6,820 KB
testcase_12 AC 14 ms
6,820 KB
testcase_13 AC 24 ms
6,816 KB
testcase_14 AC 23 ms
6,816 KB
testcase_15 AC 22 ms
6,820 KB
testcase_16 AC 24 ms
6,820 KB
testcase_17 AC 13 ms
6,820 KB
testcase_18 AC 14 ms
6,820 KB
testcase_19 AC 13 ms
6,816 KB
testcase_20 AC 14 ms
6,816 KB
testcase_21 AC 9 ms
6,816 KB
testcase_22 AC 7 ms
6,820 KB
testcase_23 AC 11 ms
6,820 KB
testcase_24 AC 11 ms
6,816 KB
testcase_25 AC 10 ms
6,820 KB
testcase_26 AC 10 ms
6,820 KB
testcase_27 AC 10 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

template <typename T> struct bellman_ford {
    struct edge {
        int from, to;
        T cost;
    };
    int V;
    vector<T> d;
    vector<edge> es;
    T inf() { return numeric_limits<T>::max() / 10; }
    bellman_ford(int node_size) : V(node_size), d(V, inf()) {}
    void add_edge(int from, int to, T cost) {
        es.push_back((edge){from, to, cost});
    }
    // sからの最短路長およびsからたどり着ける負の閉路の検出(trueなら負の閉路が存在する)
    T solve(int s) {
        int cnt = 0;
        d[s] = 0;
        while (cnt < V) {
            bool update = false;
            for (auto &e : es) {
                if (d[e.from] != inf() && d[e.to] > d[e.from] + e.cost) {
                    d[e.to] = d[e.from] + e.cost;
                    update = true;
                }
            }
            if (!update)
                break;
            cnt++;
        }
        return d[V - 1];
    }
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> use(m, 1);
    vector<int> a(m), b(m), c(m);
    rep(i, 0, m) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
    }
    rep(i, 0, q) {
        int x;
        cin >> x;
        x--;
        use[x] ^= 1;
        bellman_ford<int> bf(n);
        rep(j, 0, m) {
            if (use[j])
                bf.add_edge(a[j], b[j], -c[j]);
        }
        int ans = bf.solve(0);
        if (ans == bf.inf())
            cout << "NaN" << endl;
        else
            cout << -ans << endl;
    }
}
0