Submission #11352878

---

Source Code Expand

#include <bits/stdc++.h>
#define gcd(m,n) __gcd(m,n)
#define lcm(m,n) m*(n/gcd(m,n))
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)
#define endl '\n'
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define dbg(x) cout << #x << "  " << x << endl;

ll power(ll base, ll exp) 
{ll res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}
ll mod(ll a, ll b) {return (a % b + b) % b;}
using namespace std;

ll N,M,x,y,wt; 
ll visited[5000];
vector<ll>score;
ll scored = 0,check=0;
vector<pair<ll,ll>> *graph = new vector<pair<ll,ll>>[20000];

void DFS(ll v)
{
	visited[v] = 1;
	//cout << v << " ";
	for(ll i = 0; i < graph[v].size(); i++)
	{
		if(visited[graph[v][i].first] == 0 && graph[v][i].first == N)
		{
			scored += graph[v][i].second;
			score.push_back(scored);
			DFS(graph[v][i].first);
			visited[N] = 0;
			scored -= graph[v][i].second;
		}
		else if(visited[graph[v][i].first] == 0)
		{
			scored += graph[v][i].second;
			DFS(graph[v][i].first);
			scored -= graph[v][i].second;
		}
	}
}
bool DFSc(ll v)
{
	visited[v] = 1;
//	cout << v << " ";
	for(ll i = 0; i < graph[v].size(); i++)
	{
		ll c = graph[v][i].first;
		if(visited[c] == 0)
		{
			if(DFSc(c))
				return true;
		}
		else if(visited[c] == 1)
		{
			check = -1;
			return true;
		}
	}
	visited[v] = 2;
	return false;
}
int main() 
{
	score.clear();
	fast;
	cin>>N>>M;
	for(ll i = 0; i < M; i++)
	{
		cin>>x>>y>>wt;
		graph[x].push_back(make_pair(y,wt));
	}
	
	memset(visited,0,sizeof(visited));
	check = 0;
	for(ll i = 1; i <= N; i++)
	{
		if(visited[i] == 0 && DFSc(i))
		{
			break;
		}
	}
	
	if(check == 0)
	{
		memset(visited,0,sizeof(visited));
		DFS(1);
		sort(score.begin(),score.end(),greater<ll>());
		cout << score[0] << endl;
	}
	else
	{
		cout << "inf" << endl;
	}
 	return 0;
}

Submission Info

Judge Result