#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
int dfs (int padre, int nodo, vector<vector<int>>& listaAdy, int pop[], vector<vector<int>>& dp){
if(dp[nodo][padre] != -1) return dp[nodo][padre];
dp[nodo][padre] = pop[nodo];
for(int conexion: listaAdy[nodo]){
if(conexion != padre) dp[nodo][padre]+= dfs(nodo, conexion, listaAdy, pop, dp);
}
return dp[nodo][padre];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
vector<vector<int>> listaAdy(N);
for(int i= 0; i < N; ++i){
int a = S[i];
int b = D[i];
listaAdy[a].push_back(b);
}
vector<vector<int>> dp(N, vector<int> (N, -1));
pair<int, int> ans = make_pair(1e9, 0);
for(int ciudad = 0; ciudad < N; ++ciudad){
int act = -1e9;
for(int conex: listaAdy[ciudad]){
act = max(act, dfs(ciudad, conex, listaAdy, pp, dp));
}
ans = min(ans, make_pair(act, ciudad));
}
return ans.second;
}
