#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 = 2e6+77;
const int INF = 1e18+77;
const double eps = 1e-11;
vector<pair<int, int>> g[50009];
vector<int> ist[50009];
int dist[50009], p[50009];
bool used[50009];
void solve(){
int n;
cin >> n;
set<pair<int, int>> q;
for(int i = 1; i <= n - 1; i++){
int x, y, v;
cin >> x >> y >> v;
x++;y++;
g[x].push_back({v, y});
ist[y].push_back(x);
}
int s;
for(int i = 1; i <= n; i++){
if(ist[i].size() == 0){
s = i;
break;
}
}
for(int i = 1; i <= n; i++) dist[i] = INF;
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;
a++;b++;c++;d++;e++;
int mask[10], ans = 0;
for(int i = 1; i <= n; i++) used[i] = 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);
for(auto it : path){
if(!used[it]){
used[it] = 1;
}else{
if(it != s){
ans -= abs(dist[it] - dist[p[it]]);
}
}
}
ans += dist[mask[pos]];
}
}
cout << ans << '\n';
}
}
signed main(){
Kuanyshh;
int tt = 1;
// cin >> tt;
while(tt--){
solve();
}
}
Compilation message
roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:45: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]
45 | for(int i = 0; i < g[v].size(); i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1060 ms |
7576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
428 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Execution timed out |
1060 ms |
7576 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
