Submission #4074780

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, m, r, a, b, c, dst[1008][1008];
bool pass[1008][1008];

void warshall_floid(){
	for(ll k = 1; k <= n; k++)
		for(ll i = 1; i <= n; i++)
			for(ll j = 1; j <= n; j++)
				if(pass[i][k] && pass[k][j]){
					if(pass[i][j]){dst[i][j] = min(dst[i][k]+dst[k][j], dst[i][j]);}
					else{pass[i][j] = true; dst[i][j] = dst[i][k]+dst[k][j];}
				}
}

int main() {
	cin >> n >> m;
	for(ll i = 1; i <= n; i++){for(ll j = 1; j <= n; j++){pass[i][j] = false;}}
	for(ll i = 1; i <= n; i++){pass[i][i] = true; dst[i][i] = 0;}
	for(ll i = 1; i <= m; i++){
		cin >> a >> b >> c;
		pass[a][b] = true;
		dst[a][b] = -c;
	}
	
	warshall_floid();
	
	//for(ll i = 1; i <= n; i++){for(ll j = 1; j <= n; j++){cout << dst[i][j];}cout << endl;}
	bool roop = false;
	for(ll i = 1; i <= n; i++){if(dst[i][i] < 0){roop = true;}}
	if(roop){cout << "inf";}
	else{cout << -dst[1][n];}
	
	return 0;
}

Submission Info

Judge Result