CSES - Shared codeLink to this code: https://cses.fi/paste/e6b5aaeb18c379366707e5/
#include<bits/stdc++.h>
using namespace std;
vector<bool>vis;
void dfs(int u,int rooms,vector<int>*graph){
if(vis[u]){
return;
}
vis[u]=true;
for(int v:graph[u])dfs(v,rooms,graph);
}
int main(){
int rooms,tunnels;
cin>>rooms>>tunnels;
vis.resize(rooms+1,false);
vector<int>graph[rooms+1];
vector<array<int,3>>Tunnels(tunnels);
for(int tunnel=0;tunnel<tunnels;tunnel++){
cin>>Tunnels[tunnel][0]>>Tunnels[tunnel][1]>>Tunnels[tunnel][2];
graph[Tunnels[tunnel][0]].push_back(Tunnels[tunnel][1]);
}
dfs(1,rooms,graph);
vector<long long> score(rooms+1,-1e17);
score[1]=0;
for(int room=1;room<=rooms;room++){
for(auto &tunnel:Tunnels){
if(score[tunnel[0]]+tunnel[2]>score[tunnel[1]] and vis[tunnel[0]]){
score[tunnel[1]]=score[tunnel[0]]+tunnel[2];
}
}
}
long long ans=score[rooms];
for(int room=1;room<=rooms;room++){
for(auto &tunnel:Tunnels){
if(score[tunnel[0]]+tunnel[2]>score[tunnel[1]] and vis[tunnel[0]]){
score[tunnel[1]]=1e18;
}
}
}
if(score[rooms]!=ans){
cout<<-1;
}else{
cout<<ans;
}
return 0;
}