#include <bits/stdc++.h>
#define int long long
#define Kuanyshh ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define F first
#define S second
#pragma GCC optimize( "Ofast", "O3" , "unroll-loops")
#pragma GCC target ("sse,sse2")
using namespace std;
const int N = 1e6+77;
const int INF = 1e18+77;
const double eps = 1e-11;
void solve(){
int n;
cin >> n;
vector<pair<int, int>> g[n + 3];
vector<int> ist[n + 3];
vector<int> dist(n + 3, INF), p(n + 3);
set<pair<int, int>> q;
for(int i = 1; i <= n - 1; i++){
int x, y, v;
cin >> x >> y >> v;
g[x].push_back({v, y});
ist[y].push_back(x);
}
int s;
for(int i = 0; i < n; i++){
if(ist[i].size() == 0){
s = i;
break;
}
}
dist[s] = 0;
q.insert({dist[s], s});
while(q.size() != 0){
int v = q.begin() -> second;
q.erase(q.begin());
for(int i = 0; i < g[v].size(); i++){
int to = g[v][i].S;
int len = g[v][i].F;
if(dist[to] > dist[v] + len){
q.erase({dist[to], to});
dist[to] = dist[v] + len;
p[to] = v;
q.insert({dist[to], to});
}
}
}
int qq;
cin >> qq;
while(qq--){
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
int mask[10], ans = 0;
bool used[10];
used[a] = used[b] = used[c] = used[d] = used[e] = 0;
mask[1] = a; mask[2] = b; mask[3] = c; mask[4] = d; mask[5] = e;
for(int pos = 1; pos <= 5; pos++){
if(mask[pos] != s){
vector<int> path;
for(int v = mask[pos]; v != s; v = p[v]){
path.push_back(v);
}
path.push_back(s);
reverse(path.begin(), path.end());
for(auto it : path){
if(!used[it]){
used[it] = 1;
}else{
if(it != s){
// cout << pos << ' ' << "- " << abs(dist[it] - dist[p[it]]) << '\n';
ans -= abs(dist[it] - dist[p[it]]);
}
}
}
// cout << pos <<' ' <<"+ " << dist[mask[pos]] << '\n';
ans += dist[mask[pos]];
}
}
cout << ans << '\n';
//0 4 1 3 5
}
}
signed main(){
Kuanyshh;
int tt = 1;
// cin >> tt;
while(tt--){
solve();
}
}
Compilation message
roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < g[v].size(); i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
13140 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
11744 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
21 ms |
13140 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
