| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 764966 | vjudge1 | Roadside Advertisements (NOI17_roadsideadverts) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define int long long
const int N = 2e5 + 78 , inf = 1e19;
using namespace std;
string trans(int n , int k){
string s = "";
while(n != 0){
int d = n % k;
if(d < 10){
s = to_string(d) + s;
}
else{
s = char(d + 'A' - 10) + s;
}
n /= k;
}
return s;
}
int n , m , d[N] , q , sum = 0;
vector<pair<int , int>> g[N];
vector<int> ans;
int dj(int sta , int a1 , int a2 , int a3 , int a4){
for(int i = 0 ; i <= n ; i++)d[i] = inf;
d[sta] = 0;
int p[n + 1];
set<pair<int , int>> st;
st.insert({0 , sta});
while(st.size()){
int v = st.begin() -> second;
st.erase(st.begin());
for(int i = 0 ; i < g[v].size() ; i++){
int to = g[v][i].first , w = g[v][i].second;
int cur = d[v] + w;
if(d[to] > cur){
st.erase({d[to] , to});
d[to] = cur;
p[to] = v;
st.insert({d[to] , to});
}
}
}
return max(d[a1] , max(d[a2] , max(d[a3] , d[a4])));
}
void solve(){
cin >> n;
for(int i = 1 ; i < n ; i++){
int x, y , z;
cin >> x >> y >> z;
sum += z;
g[x].push_back({y , z});
g[y].push_back({x , z});
}
if(n != 5){
cin >> q;
while(q--){
int a1 , a2 , a3 , a4 , a5;
cin >> a1 >> a2 >> a3 >> a4 >> a5;
int mx = dj(a1 , a2 , a3 , a4 , a5);
mx = max(mx , dj(a2 , a3 , a4 , a5 , a1));
mx = max(mx , dj(a3 , a1 , a2 , a4 , a5));
mx = max(mx , dj(a4 , a1 , a2 , a3 , a5));
mx = max(mx , dj(a5 , a1 , a2 , a3 , a4));
cout << mx;
}
}
else{
cin >> q;
while(q--){
cout << sum << '\n';
}
}
}
main(){
Bekabot
int t = 1;
//cin >> t;
while(t--){
solve();
}
}