# Gold - shortcut

Shortcut

## 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);
}
}

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;
}