#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
const int MAX_SOMMET = 1e5+42, INF = 1e16;
struct Arete{
int dest, cost;
};
struct Pq{
int sommet, dist, type;
bool operator<(const Pq &autre) const {
return dist > autre.dist;
}
};
int nbSommet, nbArete;
int debOpti, finOpti, debReq, finReq;
vector<Arete> adj[MAX_SOMMET];
void input() {
cin >> nbSommet >> nbArete;
cin >> debOpti >> finOpti >> debReq >> finReq;
debOpti--; finOpti--; debReq--; finReq--;
for(int arete = 0; arete < nbArete; arete++) {
int u,v,c;
cin >> u >> v >> c;
adj[--u].push_back({--v, c});
adj[v].push_back({u, c});
}
}
bool vu[MAX_SOMMET][4] = {0};
int dist[MAX_SOMMET];
bool dansPcc[MAX_SOMMET] = {0};
void calcOrdre(int sommet) {
if(dansPcc[sommet]) {
return;
}
dansPcc[sommet] = 1;
for(auto voisin : adj[sommet]) {
if(dist[sommet] == dist[voisin.dest] + voisin.cost) {
calcOrdre(voisin.dest);
}
}
}
int rep = INF;
void pcc(int deb, int fin) {
for(int sommet = 0; sommet < MAX_SOMMET; sommet++) {
for(int type = 0; type < 4; type++) {
vu[sommet][type] = 0;
}
}
priority_queue<Pq> q;
q.push({deb, 0, 0});
if(dansPcc[deb]) {
q.push({deb, 0, 1});
q.push({deb, 0, 2});
}
while(!q.empty()) {
Pq cur = q.top();
q.pop();
if(vu[cur.sommet][cur.type]) {
continue;
}
vu[cur.sommet][cur.type] = 1;
if(deb == debOpti) {
dist[cur.sommet] = cur.dist;
}
if(cur.sommet == fin && deb == debReq && fin == finReq) {
rep = min(rep, cur.dist);
}
for(auto voisin : adj[cur.sommet]) {
if(dansPcc[voisin.dest] == 0) {
int typeNouv = 0;
if(cur.type > 0) {
typeNouv = 3;
}
q.push({voisin.dest, cur.dist + voisin.cost, typeNouv});
}
else {
if(cur.type == 0) {
q.push({voisin.dest, cur.dist + voisin.cost, 0});
q.push({voisin.dest, cur.dist + voisin.cost, 1});
q.push({voisin.dest, cur.dist + voisin.cost, 2});
}
if(cur.type == 1 && dist[cur.sommet] < dist[voisin.dest]) {
q.push({voisin.dest, cur.dist, 1});
}
if(cur.type == 2 && dist[cur.sommet] > dist[voisin.dest]) {
q.push({voisin.dest, cur.dist, 2});
}
q.push({voisin.dest, cur.dist + voisin.cost, 3});
}
}
}
}
signed main() {
input();
pcc(debOpti, finOpti);
calcOrdre(finOpti);
pcc(debReq, finReq);
cout << rep;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
619 ms |
33576 KB |
Output is correct |
2 |
Correct |
746 ms |
33688 KB |
Output is correct |
3 |
Correct |
1054 ms |
43008 KB |
Output is correct |
4 |
Correct |
615 ms |
33592 KB |
Output is correct |
5 |
Correct |
863 ms |
30204 KB |
Output is correct |
6 |
Correct |
578 ms |
36428 KB |
Output is correct |
7 |
Correct |
881 ms |
42468 KB |
Output is correct |
8 |
Correct |
898 ms |
36212 KB |
Output is correct |
9 |
Correct |
584 ms |
37000 KB |
Output is correct |
10 |
Correct |
414 ms |
37072 KB |
Output is correct |
11 |
Correct |
245 ms |
19388 KB |
Output is correct |
12 |
Correct |
545 ms |
36932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
757 ms |
34940 KB |
Output is correct |
2 |
Correct |
757 ms |
29180 KB |
Output is correct |
3 |
Correct |
751 ms |
28888 KB |
Output is correct |
4 |
Correct |
759 ms |
29064 KB |
Output is correct |
5 |
Correct |
833 ms |
29348 KB |
Output is correct |
6 |
Correct |
938 ms |
42644 KB |
Output is correct |
7 |
Correct |
1006 ms |
43012 KB |
Output is correct |
8 |
Correct |
728 ms |
29148 KB |
Output is correct |
9 |
Correct |
766 ms |
29308 KB |
Output is correct |
10 |
Correct |
702 ms |
28924 KB |
Output is correct |
11 |
Correct |
299 ms |
19252 KB |
Output is correct |
12 |
Correct |
920 ms |
42960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
8028 KB |
Output is correct |
2 |
Correct |
3 ms |
3028 KB |
Output is correct |
3 |
Correct |
3 ms |
3028 KB |
Output is correct |
4 |
Correct |
80 ms |
11044 KB |
Output is correct |
5 |
Correct |
52 ms |
9392 KB |
Output is correct |
6 |
Correct |
4 ms |
3316 KB |
Output is correct |
7 |
Correct |
7 ms |
3708 KB |
Output is correct |
8 |
Correct |
7 ms |
3544 KB |
Output is correct |
9 |
Correct |
5 ms |
3412 KB |
Output is correct |
10 |
Correct |
59 ms |
7984 KB |
Output is correct |
11 |
Correct |
2 ms |
3052 KB |
Output is correct |
12 |
Correct |
2 ms |
3028 KB |
Output is correct |
13 |
Correct |
3 ms |
3060 KB |
Output is correct |
14 |
Correct |
3 ms |
3284 KB |
Output is correct |
15 |
Correct |
4 ms |
3156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
619 ms |
33576 KB |
Output is correct |
2 |
Correct |
746 ms |
33688 KB |
Output is correct |
3 |
Correct |
1054 ms |
43008 KB |
Output is correct |
4 |
Correct |
615 ms |
33592 KB |
Output is correct |
5 |
Correct |
863 ms |
30204 KB |
Output is correct |
6 |
Correct |
578 ms |
36428 KB |
Output is correct |
7 |
Correct |
881 ms |
42468 KB |
Output is correct |
8 |
Correct |
898 ms |
36212 KB |
Output is correct |
9 |
Correct |
584 ms |
37000 KB |
Output is correct |
10 |
Correct |
414 ms |
37072 KB |
Output is correct |
11 |
Correct |
245 ms |
19388 KB |
Output is correct |
12 |
Correct |
545 ms |
36932 KB |
Output is correct |
13 |
Correct |
757 ms |
34940 KB |
Output is correct |
14 |
Correct |
757 ms |
29180 KB |
Output is correct |
15 |
Correct |
751 ms |
28888 KB |
Output is correct |
16 |
Correct |
759 ms |
29064 KB |
Output is correct |
17 |
Correct |
833 ms |
29348 KB |
Output is correct |
18 |
Correct |
938 ms |
42644 KB |
Output is correct |
19 |
Correct |
1006 ms |
43012 KB |
Output is correct |
20 |
Correct |
728 ms |
29148 KB |
Output is correct |
21 |
Correct |
766 ms |
29308 KB |
Output is correct |
22 |
Correct |
702 ms |
28924 KB |
Output is correct |
23 |
Correct |
299 ms |
19252 KB |
Output is correct |
24 |
Correct |
920 ms |
42960 KB |
Output is correct |
25 |
Correct |
69 ms |
8028 KB |
Output is correct |
26 |
Correct |
3 ms |
3028 KB |
Output is correct |
27 |
Correct |
3 ms |
3028 KB |
Output is correct |
28 |
Correct |
80 ms |
11044 KB |
Output is correct |
29 |
Correct |
52 ms |
9392 KB |
Output is correct |
30 |
Correct |
4 ms |
3316 KB |
Output is correct |
31 |
Correct |
7 ms |
3708 KB |
Output is correct |
32 |
Correct |
7 ms |
3544 KB |
Output is correct |
33 |
Correct |
5 ms |
3412 KB |
Output is correct |
34 |
Correct |
59 ms |
7984 KB |
Output is correct |
35 |
Correct |
2 ms |
3052 KB |
Output is correct |
36 |
Correct |
2 ms |
3028 KB |
Output is correct |
37 |
Correct |
3 ms |
3060 KB |
Output is correct |
38 |
Correct |
3 ms |
3284 KB |
Output is correct |
39 |
Correct |
4 ms |
3156 KB |
Output is correct |
40 |
Correct |
851 ms |
42368 KB |
Output is correct |
41 |
Correct |
555 ms |
28460 KB |
Output is correct |
42 |
Correct |
567 ms |
28472 KB |
Output is correct |
43 |
Correct |
325 ms |
16744 KB |
Output is correct |
44 |
Correct |
332 ms |
16764 KB |
Output is correct |
45 |
Correct |
1229 ms |
42480 KB |
Output is correct |
46 |
Correct |
1221 ms |
29840 KB |
Output is correct |
47 |
Correct |
546 ms |
27480 KB |
Output is correct |
48 |
Correct |
335 ms |
14804 KB |
Output is correct |
49 |
Correct |
733 ms |
35588 KB |
Output is correct |
50 |
Correct |
1045 ms |
30248 KB |
Output is correct |
51 |
Correct |
1179 ms |
42408 KB |
Output is correct |