Gold - shortcut

Debugging Help
#1

Problem Info

Shortcut
Link: here

Question

I wonder why my code run all and failing on only test case 9, I don’t know what cause failing.

What I’ve Tried

First, I use dijkstra to find shortest path from 1 to all nodes.
While dijkstra-ing, I build a tree where 1 is the root node in order to find total cows after a node for each node. Then I calculate the maximum it can get. But failed in test case 9.
I also look at the test cases, but I don’t know why sum up cows using tree cause error. It’s overflow? And if it’s, how to fix it?
I’d appreciated if some could help me.

Here is my code:

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

typedef pair<long long, long long> ll;
const int MAX_N = 10000;

long long n, m, t;
long long cows[MAX_N];
vector<ll> edge[MAX_N];
vector<int> tree[MAX_N];
int p[MAX_N];
long long tot_cows[MAX_N];
long long d[MAX_N];

void dijkstra(int s)
{
    for(int i = 0; i < n; i++) d[i] = LLONG_MAX;
    priority_queue<ll, vector<ll>, greater<ll> > pq;
    d[s] = 0;
    pq.push(ll(s, d[s]));
    while(!pq.empty()){
        long long u = pq.top().second, k = pq.top().first;
        pq.pop();
        if(k != d[u]) continue;
        if(u != 0){
            tree[p[u]].push_back(u);
        }
        for(int i = 0; i < edge[u].size(); i++){
            long long v = edge[u][i].first, w = edge[u][i].second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                p[v] = u;
                pq.push(ll(d[v], v));
            }
            else if(d[v] == d[u] + w){
                if(p[v] > u){
                    p[v] = u;
                    pq.push(ll(d[v], v));
                }
            }
        }
    }
}

long long dfs(int u)
{
    tot_cows[u] = cows[u];
    for(auto v : tree[u]){
        tot_cows[u] += dfs(v);
    }
    return tot_cows[u];
}

int main()
{
    freopen("shortcut.in","r",stdin);
    freopen("shortcut.out","w",stdout);

    cin>>n>>m>>t;
    for(int i = 0; i < n; i++) cin>>cows[i];
    for(int i = 0; i < m; i++){
        long long u, v, w; cin>>u>>v>>w;
        u--; v--;
        edge[u].push_back(ll(v, w));
        edge[v].push_back(ll(u, w));
    }

    p[0] = -1;
    dijkstra(0);
    tot_cows[0] = dfs(0); // find every all cows the node goes after

    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans = max(ans, (long long)((d[i] - t) * tot_cows[i]));
    }
    cout<<ans;

    return 0;
}
#2

\quad