제출 #1196620

#제출 시각아이디문제언어결과실행 시간메모리
1196620sunboiCrocodile's Underground City (IOI11_crocodile)C++20
46 / 100
1 ms784 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<pair<int, int>>> g; vector<int> dp, visited; set<int> goated; void dfs(int v, int par){ if (goated.count(v) == 0){ int mn = 1e9, second_mn = 1e9; visited[v] = 1; for (auto [u, w] : g[v]){ if (u == par || visited[u]) continue; dfs(u, v); int path = dp[u] + w; if (path < mn){ second_mn = mn; mn = path; }else if (path == mn){ second_mn = path; }else if (path < second_mn){ second_mn = path; } } dp[v] = second_mn; } //cout << v << ' ' << par << ' ' << dp[v] << endl; } int travel_plan(int N, int M, int R[][2], int W[], int K, int E[]){ g.resize(N); dp.resize(N, 1e9); visited.resize(N); for (int i = 0; i < M; i++){ int a = R[i][0], b = R[i][1], c = W[i]; g[a].push_back({b, c}); g[b].push_back({a, c}); } for (int i = 0; i < K; i++){ goated.insert(E[i]); dp[E[i]] = 0; } dfs(0, -1); return dp[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...