# USACO Gold 19 - Shortcut

## 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