Gold - shortcut

Problem Info

Link: here


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]));
        long long u =, k =;
        if(k != d[u]) continue;
        if(u != 0){
        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()

    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;
    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]));

    return 0;