結果

問題 No.2915 辺更新価値最大化
ユーザー SnowBeenDiding
提出日時 2024-10-04 22:56:36
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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