Investing

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

#define rep(i, a, b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll inf = LLONG_MAX;
struct Ed { int a,b,w,s() { return a<b?a:-a; }};
struct Node {ll dist=inf; int prev=-1;};

void bellmanFord(vector<Node>&nodes, vector<Ed>&eds, int s) {
    nodes[s].dist=0;
    sort(all(eds),[](Ed a, Ed b){ return a.s()<b.s();});

    int lim=sz(nodes)/2+2;
    rep(i,0,lim) for(Ed ed:eds){
        Node cur=nodes[ed.a], &dest=nodes[ed.b];
        if(abs(cur.dist)==inf)continue;
        ll d=cur.dist+ed.w;
        if(d<dest.dist){
            dest.prev=ed.a;
            dest.dist=(i<lim-1 ? d : -inf);
        }
    }
    rep(i,0,lim) for(Ed ed:eds){
        if(nodes[ed.a].dist==-inf){
            nodes[ed.b].dist=-inf;
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n,m,a,b;
    cin >> n >> m >> a >> b;
    a--;
    b--;
    vector<Ed> e(m);
    vector<Node> nodes(n);
    for (int i = 0; i < m; i++) {
        cin >> e[i].a >> e[i].b >> e[i].w;
        e[i].a--;
        e[i].b--;
        e[i].w = -e[i].w;
    }
    bellmanFord(nodes, e, a);
    if(nodes[b].dist==-inf){
        cout<<"INFINITE MONEY GLITCH";
    }else if(nodes[b].dist==inf){
        cout <<"IMPOSSIBLE";
    }else{
        cout<<-nodes[b].dist;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

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: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

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