#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
bool comp(pair<long long, int> a, pair<long long, int> b) {
return b < a;
}
bool comp2(pair<long long, pair<int, int>> a, pair<long long, pair<int, int>> b) {
return b < a;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
// buat dijkstra 2 state
// 1 state n 1 state 3 options
// option 1 -> belum pakai s->t
// option 2 -> lagi pakai s->t closing to s
// option 3 -> lagi pakai s-> t closing ke t
// option 4 -> sudah pakai s->t
long long dist[n + 1][4];
memset(dist, -1, sizeof(dist));
vector<pair<int, int>> edges[n + 1];
for(int i = 1; i <= m; ++i) {
int a, b, c;
cin >> a >> b >> c;
edges[a].push_back({b, c});
edges[b].push_back({a, c});
}
// dijkstra mulai dari u 0 ke v
// terserah v pakai yg mana
long long sdist[n + 1], tdist[n + 1];
memset(sdist, -1, sizeof(sdist));
memset(tdist, -1, sizeof(tdist));
priority_queue<pair<long long, int>, vector<pair<long long, int>>, function<bool(pair<long long, int>, pair<long long, int>)>> pq(comp);
pq.push({0, s});
while(pq.size()) {
long long d = pq.top().first; int nd = pq.top().second;
pq.pop();
if(sdist[nd] != -1)
continue;
//cout << nd << " " << d << endl;
sdist[nd] = d;
for(auto i : edges[nd]) {
if(sdist[i.first] == -1) {
pq.push({d + i.second, i.first});
}
}
}
pq.push({0, t});
while(pq.size()) {
long long d = pq.top().first; int nd = pq.top().second;
pq.pop();
if(tdist[nd] != -1)
continue;
//cout << nd << " " << d << endl;
tdist[nd] = d;
for(auto i : edges[nd]) {
if(tdist[i.first] == -1) {
pq.push({d + i.second, i.first});
}
}
}
long long act = sdist[t];
priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, function<bool(pair<long long, pair<int, int>>, pair<long long, pair<int ,int>>)>> dijkstra(comp2);
dijkstra.push(make_pair(0, make_pair(u, 0)));
while(dijkstra.size()) {
long long d = dijkstra.top().first; int nd = dijkstra.top().second.first, opt = dijkstra.top().second.second;
dijkstra.pop();
if(dist[nd][opt] != -1)
continue;
dist[nd][opt] = d;
//cout << nd << " " << opt << " " << d << endl;
if(opt == 0) {
// jadinya bisa try to use opt
// atau bs continue to use 0
for(auto i : edges[nd]) {
if(dist[i.first][0] == -1) {
dijkstra.push(make_pair(d + i.second, make_pair(i.first, 0)));
}
}
for(auto i : edges[nd]) {
if(dist[i.first][1] == -1 && tdist[nd] + sdist[i.first] + i.second == act) {
dijkstra.push(make_pair(d, make_pair(i.first, 1)));
}
}
for(auto i : edges[nd]) {
if(dist[i.first][2] == -1 && tdist[i.first] + sdist[nd] + i.second == act) {
dijkstra.push(make_pair(d, make_pair(i.first, 2)));
}
}
}
else if(opt == 3) {
// jadi cmn coba edge biasa aja
for(auto i : edges[nd]) {
if(dist[i.first][3] == -1) {
dijkstra.push(make_pair(d + i.second, make_pair(i.first, 3)));
}
}
}
else if(opt == 1) {
// coba 1 to 1
// sama coba 1 to 3
for(auto i : edges[nd]) {
if(dist[i.first][1] == -1 && tdist[nd] + sdist[i.first] + i.second == act) {
dijkstra.push(make_pair(d, make_pair(i.first, 1)));
}
}
for(auto i : edges[nd]) {
if(dist[i.first][3] == -1) {
dijkstra.push(make_pair(d + i.second, make_pair(i.first, 3)));
}
}
}
else if(opt == 2) {
for(auto i : edges[nd]) {
if(dist[i.first][2] == -1 && tdist[i.first] + sdist[nd] + i.second == act) {
dijkstra.push(make_pair(d, make_pair(i.first, 2)));
}
}
for(auto i : edges[nd]) {
if(dist[i.first][3] == -1) {
dijkstra.push(make_pair(d + i.second, make_pair(i.first, 3)));
}
}
}
}
long long tmp = 1e18;
for(int i = 0; i < 4; ++i) {
if(dist[v][i] != -1)
tmp = min(tmp, dist[v][i]);
}
cout << tmp << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
340 ms |
23344 KB |
Output is correct |
2 |
Correct |
399 ms |
22664 KB |
Output is correct |
3 |
Correct |
561 ms |
27028 KB |
Output is correct |
4 |
Correct |
333 ms |
23172 KB |
Output is correct |
5 |
Correct |
686 ms |
22328 KB |
Output is correct |
6 |
Correct |
420 ms |
23408 KB |
Output is correct |
7 |
Correct |
505 ms |
26604 KB |
Output is correct |
8 |
Correct |
479 ms |
22600 KB |
Output is correct |
9 |
Correct |
324 ms |
23532 KB |
Output is correct |
10 |
Correct |
434 ms |
23652 KB |
Output is correct |
11 |
Correct |
134 ms |
14640 KB |
Output is correct |
12 |
Correct |
513 ms |
23496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
427 ms |
22932 KB |
Output is correct |
2 |
Correct |
431 ms |
22512 KB |
Output is correct |
3 |
Correct |
460 ms |
22424 KB |
Output is correct |
4 |
Correct |
443 ms |
22444 KB |
Output is correct |
5 |
Correct |
456 ms |
22352 KB |
Output is correct |
6 |
Correct |
463 ms |
26976 KB |
Output is correct |
7 |
Correct |
495 ms |
26432 KB |
Output is correct |
8 |
Correct |
415 ms |
22520 KB |
Output is correct |
9 |
Correct |
429 ms |
22388 KB |
Output is correct |
10 |
Correct |
448 ms |
22572 KB |
Output is correct |
11 |
Correct |
142 ms |
14656 KB |
Output is correct |
12 |
Correct |
448 ms |
27000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
2780 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
47 ms |
3976 KB |
Output is correct |
5 |
Correct |
27 ms |
2756 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
3 ms |
580 KB |
Output is correct |
8 |
Correct |
4 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
456 KB |
Output is correct |
10 |
Correct |
29 ms |
2904 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
340 ms |
23344 KB |
Output is correct |
2 |
Correct |
399 ms |
22664 KB |
Output is correct |
3 |
Correct |
561 ms |
27028 KB |
Output is correct |
4 |
Correct |
333 ms |
23172 KB |
Output is correct |
5 |
Correct |
686 ms |
22328 KB |
Output is correct |
6 |
Correct |
420 ms |
23408 KB |
Output is correct |
7 |
Correct |
505 ms |
26604 KB |
Output is correct |
8 |
Correct |
479 ms |
22600 KB |
Output is correct |
9 |
Correct |
324 ms |
23532 KB |
Output is correct |
10 |
Correct |
434 ms |
23652 KB |
Output is correct |
11 |
Correct |
134 ms |
14640 KB |
Output is correct |
12 |
Correct |
513 ms |
23496 KB |
Output is correct |
13 |
Correct |
427 ms |
22932 KB |
Output is correct |
14 |
Correct |
431 ms |
22512 KB |
Output is correct |
15 |
Correct |
460 ms |
22424 KB |
Output is correct |
16 |
Correct |
443 ms |
22444 KB |
Output is correct |
17 |
Correct |
456 ms |
22352 KB |
Output is correct |
18 |
Correct |
463 ms |
26976 KB |
Output is correct |
19 |
Correct |
495 ms |
26432 KB |
Output is correct |
20 |
Correct |
415 ms |
22520 KB |
Output is correct |
21 |
Correct |
429 ms |
22388 KB |
Output is correct |
22 |
Correct |
448 ms |
22572 KB |
Output is correct |
23 |
Correct |
142 ms |
14656 KB |
Output is correct |
24 |
Correct |
448 ms |
27000 KB |
Output is correct |
25 |
Correct |
33 ms |
2780 KB |
Output is correct |
26 |
Correct |
2 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
47 ms |
3976 KB |
Output is correct |
29 |
Correct |
27 ms |
2756 KB |
Output is correct |
30 |
Correct |
2 ms |
468 KB |
Output is correct |
31 |
Correct |
3 ms |
580 KB |
Output is correct |
32 |
Correct |
4 ms |
596 KB |
Output is correct |
33 |
Correct |
2 ms |
456 KB |
Output is correct |
34 |
Correct |
29 ms |
2904 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
379 ms |
27652 KB |
Output is correct |
41 |
Correct |
309 ms |
22324 KB |
Output is correct |
42 |
Correct |
344 ms |
22356 KB |
Output is correct |
43 |
Correct |
172 ms |
14784 KB |
Output is correct |
44 |
Correct |
153 ms |
14792 KB |
Output is correct |
45 |
Correct |
538 ms |
26204 KB |
Output is correct |
46 |
Correct |
526 ms |
25864 KB |
Output is correct |
47 |
Correct |
331 ms |
22976 KB |
Output is correct |
48 |
Correct |
206 ms |
14136 KB |
Output is correct |
49 |
Correct |
381 ms |
27048 KB |
Output is correct |
50 |
Correct |
503 ms |
26104 KB |
Output is correct |
51 |
Correct |
545 ms |
26048 KB |
Output is correct |