# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
366573 | 2021-02-14T15:08:28 Z | Alma | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KB |
#include <iostream> #include <cmath> #include <vector> #include <algorithm> #include <grader.cpp> #include <traffic.h> using namespace std; typedef long long int ll; vector<vector<int>> graph; vector<ll> cost; vector<bool> visited; vector<vector<ll>> DP; void re_assign (int idx) { visited.assign(5, false); visited[idx] = true; } ll traffic (int prevCity, int city) { if (DP[prevCity][city] != -1) return DP[prevCity][city]; DP[prevCity][city] = cost[city]; visited[city] = true; for (int road: graph[city]) { if (!visited[road]) DP[prevCity][city] += traffic(city, road); } return DP[prevCity][city]; } int LocateCenter (int N, int P[], int S[], int D[]) { graph.assign(N, vector<int> ()); cost.clear(); DP.assign(N, vector<ll> (N, -1)); for (int i = 0; i < N; i++) { graph[S[i]].push_back(D[i]); graph[D[i]].push_back(S[i]); cost.push_back(P[i]); } vector<pair<ll, int>> maximums (N); ll congestion = 0; for (int city = 0; city < N; city++) { ll maxCongestion = -1; re_assign(city); for (int road: graph[city]) { congestion = traffic (city, road); maxCongestion = max(maxCongestion, congestion); } maximums[city].first = maxCongestion; maximums[city].second = city; } sort (maximums.begin(), maximums.end()); pair<ll, int> arenaCity = *min_element(maximums.begin(), maximums.end()); return arenaCity.second; }