\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法 0:
コストを -1 倍することで，min cost の問題に帰着できる．
ただし，負のコストがあるため，Dijikstra は使えない． Bellman-Ford に近い解法なら，負のサイクルも検出できて \(O(NM)\) . 負のサイクルが存在しない場合は，最大で path の長さが \(N-1\). 負のサイクルが存在するなら，最大で cycle の長さが \(N\).
まず，暫定的な min dist を求める． これは edge の更新を \(N-1\) 回繰り返せば十分． 暫定的なというのは，もし負のサイクルが無い場合の min dist であるという意味．
次に，負のサイクルを検出する． Vertex \(i\) に対して，\(i\) を含むサイクルがあるかを判定する． もしあるのなら， edge の更新を \(N\) 回繰り返しても min dist が更新され続ける． もしなければ，\(N\) 回以内で更新がストップする．
解法 1:
DFS で負のサイクルを検出する方法もある．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
vector<tuple<ll,ll,ll>> ed;
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a, --b;
ed.emplace_back(a,b,-c); // *-1 で min const
}
vll dis(n, INFL);
dis[0] = 0;
rep(_,n-1){
for(auto [a,b,c]:ed){
chmin(dis[b], dis[a] + c);
}
}
rep(_,n){
for(auto [a,b,c]:ed){
if(chmin(dis[b], dis[a] + c)) nega[b] = true;
}
}
if(nega[n-1]) cout << "inf" << endl;
else cout << -dis[n-1] << endl;
return 0;
}
