結果

問題 No.2712 Play more!
ユーザー shinchan
提出日時 2024-03-31 15:17:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,042 bytes
コンパイル時間 2,329 ms
コンパイル使用メモリ 208,524 KB
最終ジャッジ日時 2025-02-20 17:48:37
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto&& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 55);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;

class random_devicer {
	int seed;
	std::mt19937 engine;

public:
	random_devicer(const int seed = 0): seed(seed), engine(seed) {}

	// [lower, upper] 中の整数から一様ランダムに選ぶ。
	int next(int lower, int upper) {
		std::uniform_int_distribution<> dist(lower, upper);
		return dist(engine);
	}
	std::vector<int> next(int n, int lower, int upper) {
		std::vector<int> a(n);
		for(auto& e: a) e = next(lower, upper);
		return std::move(a);
	}

	bool next_bool() { return next(0, 1); }

	// [lower, upper] 中の実数から一様ランダムに選ぶ。
	double next_double(double lower, double upper) {
		std::uniform_real_distribution<> dist(lower, upper);
		return dist(engine);
	}

	// char
	char next_char_lower_case() { return next('a', 'z'); }
	char next_char_upper_case() { return next('A', 'Z'); }
	char next_char() {
		if(next_bool()) return next_char_lower_case();
		return next_char_upper_case();
	}
	char next_char(const std::string& chars) {
		assert(not chars.empty());
		return chars[next(0, chars.size() - 1)];
	}

	// string
	std::string next_string_lower_case(const int len) {
		std::string s(len, ' ');
		for(auto& c: s) c = next_char_lower_case();
		return std::move(s);
	}
	std::string next_string_upper_case(const int len) {
		std::string s(len, ' ');
		for(auto& c: s) c = next_char_upper_case();
		return std::move(s);
	}
	std::string next_string(const int len) {
		std::string s(len, ' ');
		for(auto& c: s) c = next_char();
		return std::move(s);
	}
	std::string next_string(const int len, const std::string& chars) {
		std::string s(len, ' ');
		for(auto& c: s) c = next_char(chars);
		return std::move(s);
	}

	// 頂点数 order の木を生成する。
	// p[i] := 頂点 i + 1 の親
	std::vector<int> next_tree(const int order) {
		std::vector<int> p(order - 1);
		for(size_t i = 0; i < p.size(); i++) p[i] = next(0, i);
		return std::move(p);
	}

	// 頂点数 order 辺数 size のグラフを生成する。
	std::vector<std::pair<int, int>> next_graph(const int order, const int size,
								bool is_connected = true,
								bool is_simple = true)
	{
		std::vector<std::pair<int, int>> edges;
		std::set<std::pair<int, int>> edges_set;
		if(is_connected) {
			assert(order - 1 <= size);

			auto p = next_tree(order);
			for(size_t i = 0; i < p.size(); i++) {
				edges.push_back({p[i], i + 1});
				edges_set.insert({p[i], i + 1});
				edges_set.insert({i + 1, p[i]});
			}
		}

		while((int)edges.size() != size) {
			if(is_simple) {
				int a = next(0, order - 1);
				int b = next(a + 1, order - 1);
				if(edges_set.count({a, b})) continue;

				edges.push_back({a, b});
				edges_set.insert({a, b});
				edges_set.insert({b, a});
			} else {
				int a = next(0, order - 1);
				int b = next(0, order - 1);

				edges.push_back({a, b});
				edges_set.insert({a, b});
				edges_set.insert({b, a});
			}
		}

		return std::move(edges);
	}

	// 頂点数 order のなもりグラフを生成する。
	std::vector<std::pair<int, int>> next_namori(const int order) {
		return next_graph(order, order);
	}
};

// random_devicer rnd(seed);
// rnd.next(0, n) [0, n]
bool flag = 0;
//bellman_ford
template <typename T>
std::vector<ll> bellman_ford(T &G, int start, int lim = -1){
    random_devicer rnd(0);
    // T -> vector<vector<pair<ll, int or ll>>> 
    // edge pair<ll, ll> -> pair<cost, to>
    int n = G.size();
    std::vector<ll> dis(n, (1LL << 59));
    dis[start] = 0;
    
    lim = 40000;

    for(int i = 0; i < lim; i ++) {
        bool update = 0;
        for(int j = 0; j < n; j ++) {
            for(auto [cost, to] : G[j]) {
                if(dis[j] + cost < dis[to]) {
                    dis[to] = dis[j] + cost;
                    if(i >= 15000 and to == n - 1) {
                        if(dis[to] <  (1LL << 30) * (ll)rnd.next(-1000000000, 1000000000)) {
                            flag = 1;
                            return dis;
                        }
                    }
                    
                    update = 1;
                }
            }
        }
        if(!update) break;
    }
    return dis; 
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<vector<pair<ll, ll>>> v(n * 2);
    rep(i, m) {
        ll x, y, c;
        cin >> x >> y >> c;
        x --; y --;
        v[x * 2 + 1].push_back({c, y * 2});
    }
    rep(i, n) v[i*2].push_back({-a[i], i*2+1});

    auto ret = bellman_ford(v, 0);
    if(flag) {
        cout << "inf" << endl;
        return 0;
    }
    assert(-(1LL << 30) * n <= ret.back() and ret.back() <= (1LL << 30) * n);
    cout << - ret.back() << endl;
    return 0;
}
0