結果

問題 No.2712 Play more!
コンテスト
ユーザー Nyaa Uruzu
提出日時 2025-12-04 21:59:53
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 2,302 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,092 ms
コンパイル使用メモリ 283,540 KB
実行使用メモリ 7,840 KB
最終ジャッジ日時 2025-12-04 22:00:00
合計ジャッジ時間 6,077 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (long long i=0;i<(ll)n;i++)
#define loop(i,m,n) for(long long i=m;i<=(ll)n;i++)
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define inf 4000000000000000000LL
#define mod 998244353LL

//グリッド問題等用
vl dx={1,0,-1,0};
vl dy={0,1,0,-1};

//グラフgの頂点startからの最短経路を全ての頂点に対して求める。
//到達不可負はinf,経路上に負閉路があれば-inf
//pairの順序は{行き先,コスト}
vl bellman_ford(vector<vector<pair<ll,ll>>> &g, ll start){
    ll n = g.size();
    vl dist(n, inf);
    dist[start] = 0;

    // 1. 通常の Bellman-Ford: n-1 回緩和
    rep(iter, n-1){
        bool updated = false;
        rep(u, n){
            if (dist[u] == inf || dist[u] == -inf) continue;
            for (auto &e : g[u]){
                ll v = e.first;
                ll c = e.second;
                if (dist[v] > dist[u] + c){
                    dist[v] = dist[u] + c;
                    updated = true;
                }
            }
        }
        if (!updated) break; // もう更新されないなら終了
    }

    // 2. 負閉路の検出＆-inf 伝播
    // 追加で n 回まわして、負閉路から到達可能な頂点を -inf にする
    rep(iter, n){
        rep(u, n){
            if (dist[u] == inf) continue;
            for (auto &e : g[u]){
                ll v = e.first;
                ll c = e.second;

                // すでに -inf なら先にも伝播
                if (dist[u] == -inf){
                    if (dist[v] != -inf){
                        dist[v] = -inf;
                    }
                    continue;
                }

                // まだ短くできるなら、u->v は負閉路の影響を受けている
                if (dist[v] > dist[u] + c){
                    dist[v] = -inf;
                }
            }
        }
    }

    return dist;
}

int main(){
	ll n,m;
	cin>>n>>m;
	vl d(n);
	rep(i,n)cin>>d[i];
	
	vector<vector<pair<ll,ll>>> g(n);
	rep(i,m){
		ll a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		g[a].push_back({b,c-d[a]});
	}

	vl ans=bellman_ford(g,0);
	if(ans[n-1]==-inf){
		cout<<"inf"<<endl;
	}else{
		cout<<d[n-1]-ans[n-1]<<endl;
	}
	return 0;
}
0