#include <iostream>
#include<vector>
#include<set>
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define int long long
const int N = 5e4 + 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];
int dj(int sta , int fin){
for(int i = 0 ; i <= n ; i++)d[i] = inf;
d[sta] = 0;
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;
st.insert({d[to] , to});
}
}
}
if(d[fin] != inf)return d[fin];
else return 0;
}
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});
}
cin >> q;
while(q--){
int a[6] , mx = 0;
cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5];
for(int i = 1 ; i <= 5 ; i++){
for(int j = 1 ; j <= 5 ; j++){
if(i != j)mx = max(mx , dj(a[i] , a[j]));
}
}
cout << mx << '\n';
}
}
main(){
Bekabot
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
Compilation message
roadsideadverts.cpp:9:32: warning: overflow in conversion from 'double' to 'long long int' changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
9 | const int N = 5e4 + 78 , inf = 1e19;
| ^~~~
roadsideadverts.cpp: In function 'long long int dj(long long int, long long int)':
roadsideadverts.cpp:36:22: 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]
36 | for(int i = 0 ; i < g[v].size() ; i++){
| ~~^~~~~~~~~~~~~
roadsideadverts.cpp: At global scope:
roadsideadverts.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
72 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1083 ms |
4180 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
4792 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Execution timed out |
1083 ms |
4180 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
