#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
vector<vector<pair<int,ll> > >listaAdy;
priority_queue<pair<ll,int> >pq;
vector<ll>Udist, Vdist, distancia;
vector<vector<int> >padre;
ll ans;
int N, M, S, T, U, V;
vector<pair<ll,ll> >mindist;
vector<bool>visitado;
void resolver (int nodo){
visitado[nodo]=true;
mindist[nodo].first=Udist[nodo];
mindist[nodo].second=Vdist[nodo];
for (int i=0; i<padre[nodo].size(); i++){
int pad=padre[nodo][i];
if (visitado[pad]==false) resolver(pad);
ll x=min(Udist[nodo], mindist[pad].first);
ll y=min(Vdist[nodo], mindist[pad].second);
if (mindist[nodo].first+mindist[nodo].second>x+y){
mindist[nodo].first=x;
mindist[nodo].second=y;
}
}
return;
}
int main(){
cin>>N>>M;
cin>>S>>T;
cin>>U>>V;
S--; T--; U--; V--;
listaAdy.resize(N);
while (M--){
int u, v;
ll c;
cin>>u>>v>>c;
u--; v--;
listaAdy[u].push_back(make_pair(v, c));
listaAdy[v].push_back(make_pair(u, c));
}
Udist.assign(N, 1e18);
Vdist.assign(N, 1e18);
distancia.assign(N, 1e18);
Udist[U]=0;
Vdist[V]=0;
distancia[S]=0;
//Distancia más corta de U al resto de nodos.
pq.push(make_pair(0, U));
while (!pq.empty()){
ll d=-pq.top().first;
int u=pq.top().second;
pq.pop();
if (Udist[u]<d) continue;
for (auto vec: listaAdy[u]){
int v=vec.first;
ll c=vec.second;
if (Udist[v]>Udist[u]+c){
Udist[v]=Udist[u]+c;
pq.push(make_pair(-Udist[v], v));
}
}
}
//Distancia más corta de V al resto de nodos.
pq.push(make_pair(0, V));
while (!pq.empty()){
ll d=-pq.top().first;
int u=pq.top().second;
pq.pop();
if (Vdist[u]<d) continue;
for (auto vec: listaAdy[u]){
int v=vec.first;
ll c=vec.second;
if (Vdist[v]>Vdist[u]+c){
Vdist[v]=Vdist[u]+c;
pq.push(make_pair(-Vdist[v], v));
}
}
}
//Camino más corto entre S i T guardando todos los caminos.
padre.resize(N);
pq.push(make_pair(0, S));
while (!pq.empty()){
ll d=-pq.top().first;
int u=pq.top().second;
pq.pop();
if (distancia[u]<d) continue;
for (auto vec: listaAdy[u]){
int v=vec.first;
ll c=vec.second;
if (distancia[v]>distancia[u]+c){
distancia[v]=distancia[u]+c;
padre[v].clear();
padre[v].push_back(u);
pq.push(make_pair(-distancia[v], v));
}else if (distancia[v]==distancia[u]+c) padre[v].push_back(u);
}
}
mindist.assign(N, make_pair(1e18, 1e18));
visitado.assign(N, false);
ans=Udist[V];
resolver(T);
ans=min(ans, mindist[T].first+mindist[T].second);
cout<<ans<<endl;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void resolver(int)':
commuter_pass.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i=0; i<padre[nodo].size(); i++){
| ~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
263 ms |
22836 KB |
Output is correct |
2 |
Correct |
290 ms |
22652 KB |
Output is correct |
3 |
Correct |
272 ms |
30420 KB |
Output is correct |
4 |
Correct |
282 ms |
26508 KB |
Output is correct |
5 |
Correct |
276 ms |
25968 KB |
Output is correct |
6 |
Correct |
280 ms |
26720 KB |
Output is correct |
7 |
Correct |
336 ms |
26368 KB |
Output is correct |
8 |
Correct |
268 ms |
26288 KB |
Output is correct |
9 |
Correct |
294 ms |
26936 KB |
Output is correct |
10 |
Correct |
254 ms |
26868 KB |
Output is correct |
11 |
Correct |
107 ms |
21684 KB |
Output is correct |
12 |
Correct |
309 ms |
26912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
24512 KB |
Output is correct |
2 |
Correct |
277 ms |
24532 KB |
Output is correct |
3 |
Correct |
285 ms |
24228 KB |
Output is correct |
4 |
Correct |
268 ms |
24520 KB |
Output is correct |
5 |
Correct |
269 ms |
25220 KB |
Output is correct |
6 |
Correct |
280 ms |
26208 KB |
Output is correct |
7 |
Correct |
280 ms |
26820 KB |
Output is correct |
8 |
Correct |
295 ms |
24524 KB |
Output is correct |
9 |
Correct |
309 ms |
25036 KB |
Output is correct |
10 |
Correct |
352 ms |
24232 KB |
Output is correct |
11 |
Correct |
111 ms |
20836 KB |
Output is correct |
12 |
Correct |
317 ms |
26504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
1624 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
26 ms |
3856 KB |
Output is correct |
5 |
Correct |
14 ms |
2136 KB |
Output is correct |
6 |
Correct |
2 ms |
424 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
3 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
13 ms |
2112 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
436 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
263 ms |
22836 KB |
Output is correct |
2 |
Correct |
290 ms |
22652 KB |
Output is correct |
3 |
Correct |
272 ms |
30420 KB |
Output is correct |
4 |
Correct |
282 ms |
26508 KB |
Output is correct |
5 |
Correct |
276 ms |
25968 KB |
Output is correct |
6 |
Correct |
280 ms |
26720 KB |
Output is correct |
7 |
Correct |
336 ms |
26368 KB |
Output is correct |
8 |
Correct |
268 ms |
26288 KB |
Output is correct |
9 |
Correct |
294 ms |
26936 KB |
Output is correct |
10 |
Correct |
254 ms |
26868 KB |
Output is correct |
11 |
Correct |
107 ms |
21684 KB |
Output is correct |
12 |
Correct |
309 ms |
26912 KB |
Output is correct |
13 |
Correct |
275 ms |
24512 KB |
Output is correct |
14 |
Correct |
277 ms |
24532 KB |
Output is correct |
15 |
Correct |
285 ms |
24228 KB |
Output is correct |
16 |
Correct |
268 ms |
24520 KB |
Output is correct |
17 |
Correct |
269 ms |
25220 KB |
Output is correct |
18 |
Correct |
280 ms |
26208 KB |
Output is correct |
19 |
Correct |
280 ms |
26820 KB |
Output is correct |
20 |
Correct |
295 ms |
24524 KB |
Output is correct |
21 |
Correct |
309 ms |
25036 KB |
Output is correct |
22 |
Correct |
352 ms |
24232 KB |
Output is correct |
23 |
Correct |
111 ms |
20836 KB |
Output is correct |
24 |
Correct |
317 ms |
26504 KB |
Output is correct |
25 |
Correct |
14 ms |
1624 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
26 ms |
3856 KB |
Output is correct |
29 |
Correct |
14 ms |
2136 KB |
Output is correct |
30 |
Correct |
2 ms |
424 KB |
Output is correct |
31 |
Correct |
2 ms |
604 KB |
Output is correct |
32 |
Correct |
3 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
13 ms |
2112 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
436 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
2 ms |
348 KB |
Output is correct |
39 |
Correct |
2 ms |
348 KB |
Output is correct |
40 |
Correct |
287 ms |
26876 KB |
Output is correct |
41 |
Correct |
281 ms |
26828 KB |
Output is correct |
42 |
Correct |
275 ms |
26932 KB |
Output is correct |
43 |
Correct |
128 ms |
22244 KB |
Output is correct |
44 |
Correct |
126 ms |
22352 KB |
Output is correct |
45 |
Correct |
318 ms |
25732 KB |
Output is correct |
46 |
Correct |
259 ms |
26284 KB |
Output is correct |
47 |
Correct |
252 ms |
26692 KB |
Output is correct |
48 |
Correct |
103 ms |
19320 KB |
Output is correct |
49 |
Correct |
245 ms |
26440 KB |
Output is correct |
50 |
Correct |
357 ms |
25876 KB |
Output is correct |
51 |
Correct |
248 ms |
25692 KB |
Output is correct |