Investing

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

void dfs(int node, vector<int>& visited, vector<vector<pair<int, int>>>& adj)
{
    if (visited[node])
        return;
    visited[node] = true;
    for (auto [neigh, weight] : adj[node])
        dfs(neigh, visited, adj);
}

signed main() {
    int n, m, a, b;
    cin >> n >> m>> a >> b;
    a--;b--;

    vector<vector<pair<int, int>>> adj = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>());
    for (int i = 0; i < m; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        x--;y--;
        adj[x].push_back({y, w});

    }

    vector<set<int>> forcedUpdate(n);
    vector<int> currentM(n, INT_MIN);
    currentM[a] = 0;
    priority_queue<pair<int, int>> pq;
    vector<int> glitch(n, false);

    pq.push({0, a});
    while (!pq.empty())
    {
        auto [weight, node] = pq.top();
        pq.pop();

        if (weight != currentM[node])
            continue;

        //cout << "On node " << node << " with " << weight << "\n";
        for (auto [neigh, cost] : adj[node])
        {
            if (weight + cost > currentM[neigh])
            {
                if (forcedUpdate[neigh].find(node) != forcedUpdate[neigh].end())
                {
                    glitch[neigh] = true;
                }
                else
                {
                    currentM[neigh] = weight + cost;
                    pq.push({weight + cost, neigh});
                    forcedUpdate[neigh].insert(node);
                }
            }
        }
    }

    set<int> glitches;
    for (int i = 0; i < n; i++)
    {
        if (glitch[i])
            glitches.insert(i);
    }
    for (int node : glitches)
    {
        glitch[node] = false;
        dfs(node, glitch, adj);
    }

    if (glitch[b])
    {
        cout << "INFINITE MONEY GLITCH";
        return 0;
    }
    if (currentM[b] == INT_MIN)
    {
        cout << "IMPOSSIBLE";
    }
    else
    {
        cout << currentM[b];
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: ACCEPTED

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: ACCEPTED

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: ACCEPTED

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: ACCEPTED

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED