USACO Gold 19 - Shortcut

Debugging Help
#1

Problem Info

USACO Gold Shortcut

What I’ve Tried

I’ve tried stress testing, changing ints to long longs, but nothing’s been working so far. I’m getting test cases 1, 2, 3, and 10.

My Work

#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define MAXN 10005
#define MAXM 50005

class Edge { // edges
    public:
        int a, b;
        int d;
};
class Field { //fields
    public:
        int id, c, p;
        long long d = -1, s = -1; // d = dist to field 1, s = sum of all cows that cross through in getting to field 1
};

int N, M, T;
Field F[MAXN];
vector<int> C[MAXN];
vector<Edge> E[MAXN];
long long S;

struct cmpF // compare fields by distance in a set(acting as a queue)
{
	bool operator()(int a, int b) const
	{
		return F[a].d < F[b].d;
	}
};

long long dfs(int i){ // dfs on # of cows crossing through field i; we store prev calculated values in F[i].s
    if(F[i].s != -1) return F[i].s;
    if(C[i].empty()) return (F[i].s = F[i].c);

    F[i].s = F[i].c;
    for(int c : C[i]){
        F[i].s += dfs(c);
    }

    return F[i].s;
}

int main(){
    // get data
    cin >> N >> M >> T;
    for(int i = 1; i <= N; i++) {
        cin >> F[i].c;
        F[i].id = i;
    }
    for(int i = 1; i <= M; i++){
        int a, b, d;
        cin >> a >> b >> d;
        Edge e1, e2;
        e1.a = e2.b = a;
        e1.b = e2.a = b;
        e1.d = e2.d = d;
        E[e1.a].push_back(e1);
        E[e2.a].push_back(e2);
    }
    
    bool v[MAXN];
    fill(v, v + MAXN - 1, false);
    set<int, cmpF> q;
    F[1].d = 0; q.insert(1);
    // run dijkstra's
    while(!q.empty()){
        Field f = F[*q.begin()];
        q.erase(q.begin());
        if(v[f.id]) continue;
        v[f.id] = true;

        for(Edge e : E[f.id]){
            if(v[e.b]) continue;
            if(F[e.b].d == -1 || F[e.b].d > f.d + e.d || /*pick the lexicographically shortest route*/  (F[e.b].d == f.d + e.d && F[e.b].p > f.id)) {
                F[e.b].d = f.d + e.d;
                F[e.b].p = f.id;
                if(q.find(e.b) != q.end()) q.erase(e.b);
                q.insert(e.b);
            }
        }

        C[f.p].push_back(f.id); // C[i] = all children of field i; this will help us in our future dfs
    }

    // dfs; store maximum saved time w/ shortcut in S
    S = 0;
    for(int i = 1; i <= N; i++) {
        S = max(S, (long long)dfs(i) * (F[i].d - T));
    }

    cout << S << endl;
}

Above is my commented code; I use dijkstra’s with a sorted set + dfs

#2

\quad