High Score

You play a game consisting of n rooms and m tunnels. Your initial score is 0, and each tunnel increases your score by x where x may be both positive or negative. You may go through a tunnel several times.

Your task is to walk from room 1 to room n. What is the maximum score you can get?

Example:

Input:  n = 4, m = 5, edges = {{1, 2, 3}, {2, 4, -1}, {1, 3, -2}, {3, 4, 7}, {1, 4, 4}}
Output: 5

Approach

C++

#include <bits/stdc++.h>
using namespace std;

long long dis[2505];
const long long M = 1e16;
vector<long long> adj[2505], adj2[2505];
bool vis[2505], vis2[2505];
void dfs(long long s)
{

    //if already visited
    if (vis[s])
        return;

    //mark as visted
    vis[s] = 1;

    //call for all the adjacency list
    //of current node
    for (auto i : adj[s])
        dfs(i);
}
void dfs2(long long s)
{

    //if already visted
    if (vis2[s])
        return;

    //mark as visted
    vis2[s] = 1;

    //call for all the adjacency list of the current
    //node
    for (auto i : adj2[s])
        dfs2(i);
}
long long highScore(long long n, long long m, vector<vector<long long>> &edges)
{

    for (long long i = 1; i <= n; i++)
        dis[i] = M;
    dis[1] = 0;
    for (long long i = 0; i < m; i++)
    {
        long long a = edges[i][0];
        long long b = edges[i][1];

        adj[a].push_back(b);
        adj2[b].push_back(a);
    }
    dfs(1);
    dfs2(n);
    for (long long i = 0; i < n; i++)
    {

        for (auto edge : edges)
        {
            long long a = edge[0];
            long long b = edge[1];
            long long w = -edge[2];
            if (dis[b] > dis[a] + w)
            {
                dis[b] = dis[a] + w;
                if (i == n - 1 && vis[b] && vis2[b])
                {
                    return -1;
                }
            }
        }
    }
    return -dis[n];
}
int main()
{
    long long n = 4, m = 5;

    vector<vector<long long>> edges = {{1, 2, 3},
                                       {2, 4, -1},
                                       {1, 3, -2},
                                       {3, 4, 7},
                                       {1, 4, 4}};

    cout << highScore(n, m, edges) << "\n";

    return 0;
}