#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MAXN = 1e5+5;
const int MAXM = 2e5+5;
int N,M,S,T,U,V;
vector<ii> al[4*MAXN];
ll d[4*MAXN];
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
vector<int> p[4*MAXN];
queue<int> q;
ll sssp(int S, int T, bool save) {
if (save) FOR(i,1,N) p[i].clear();
memset(d,-1,sizeof d);
d[S] = 0; pq.emplace(0,S);
while (!pq.empty()) {
int u = pq.top().sc; ll w = pq.top().fi; pq.pop();
for (auto v : al[u]) {
ll x = w+(ll)v.sc;
if (d[v.fi] == -1 || x < d[v.fi]) {
d[v.fi] = x;
if (save) p[v.fi].clear(), p[v.fi].push_back(u);
pq.emplace(x,v.fi);
} else if (x == d[v.fi]) {
if (save) p[v.fi].push_back(u);
}
}
}
//cout << "D " << S << " -> " << T << " = " << d[T] << endl;
return d[T];
}
void build(int S, int x) {
memset(d,0,sizeof d);
q.push(S);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : p[u]) {
al[v+x].emplace_back(u+x,0);
//cout << "\t\tADD " << v << " to " << u << " x " << x << endl;
if (!d[v]) {
d[v] = 1;
q.push(v);
}
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
cin >> S >> T;
cin >> U >> V;
FOR(i,1,M){
int A,B,C; cin >> A >> B >> C;
//cout << "E " << A << " " << B << " :: " << C << " (" << i*2 << ")" << endl;
//cout << "E " << B << " " << A << " :: " << C << " (" << i*2+1 << ")" << endl;
al[A].emplace_back(B,C);
al[B].emplace_back(A,C);
al[A+3*N].emplace_back(B+3*N,C);
al[B+3*N].emplace_back(A+3*N,C);
}
FOR(A,1,N){
al[A].emplace_back(A+N,0);
al[A].emplace_back(A+2*N,0);
al[A+N].emplace_back(A+3*N,0);
al[A+2*N].emplace_back(A+3*N,0);
}
sssp(S,T,1);
build(T,N);
sssp(T,S,1);
build(S,2*N);
cout << sssp(U,V+3*N,0) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1305 ms |
58076 KB |
Output is correct |
2 |
Correct |
1298 ms |
60592 KB |
Output is correct |
3 |
Correct |
1296 ms |
63132 KB |
Output is correct |
4 |
Correct |
1277 ms |
61024 KB |
Output is correct |
5 |
Correct |
1311 ms |
61052 KB |
Output is correct |
6 |
Correct |
1328 ms |
61160 KB |
Output is correct |
7 |
Correct |
1332 ms |
60608 KB |
Output is correct |
8 |
Correct |
1369 ms |
60796 KB |
Output is correct |
9 |
Correct |
1239 ms |
60900 KB |
Output is correct |
10 |
Correct |
1059 ms |
63552 KB |
Output is correct |
11 |
Correct |
718 ms |
52116 KB |
Output is correct |
12 |
Correct |
1372 ms |
60988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1337 ms |
58044 KB |
Output is correct |
2 |
Correct |
1373 ms |
60488 KB |
Output is correct |
3 |
Correct |
1411 ms |
60740 KB |
Output is correct |
4 |
Correct |
1347 ms |
60372 KB |
Output is correct |
5 |
Correct |
1326 ms |
60260 KB |
Output is correct |
6 |
Correct |
1296 ms |
61152 KB |
Output is correct |
7 |
Correct |
1385 ms |
62868 KB |
Output is correct |
8 |
Correct |
1417 ms |
60372 KB |
Output is correct |
9 |
Correct |
1405 ms |
60260 KB |
Output is correct |
10 |
Correct |
1433 ms |
60492 KB |
Output is correct |
11 |
Correct |
709 ms |
52068 KB |
Output is correct |
12 |
Correct |
1373 ms |
61212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
24440 KB |
Output is correct |
2 |
Correct |
23 ms |
22392 KB |
Output is correct |
3 |
Correct |
23 ms |
22396 KB |
Output is correct |
4 |
Correct |
47 ms |
25976 KB |
Output is correct |
5 |
Correct |
34 ms |
24056 KB |
Output is correct |
6 |
Correct |
24 ms |
22492 KB |
Output is correct |
7 |
Correct |
25 ms |
22520 KB |
Output is correct |
8 |
Correct |
26 ms |
22520 KB |
Output is correct |
9 |
Correct |
24 ms |
22520 KB |
Output is correct |
10 |
Correct |
35 ms |
24056 KB |
Output is correct |
11 |
Correct |
24 ms |
22392 KB |
Output is correct |
12 |
Correct |
24 ms |
22392 KB |
Output is correct |
13 |
Correct |
24 ms |
22392 KB |
Output is correct |
14 |
Correct |
24 ms |
22392 KB |
Output is correct |
15 |
Correct |
24 ms |
22392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1305 ms |
58076 KB |
Output is correct |
2 |
Correct |
1298 ms |
60592 KB |
Output is correct |
3 |
Correct |
1296 ms |
63132 KB |
Output is correct |
4 |
Correct |
1277 ms |
61024 KB |
Output is correct |
5 |
Correct |
1311 ms |
61052 KB |
Output is correct |
6 |
Correct |
1328 ms |
61160 KB |
Output is correct |
7 |
Correct |
1332 ms |
60608 KB |
Output is correct |
8 |
Correct |
1369 ms |
60796 KB |
Output is correct |
9 |
Correct |
1239 ms |
60900 KB |
Output is correct |
10 |
Correct |
1059 ms |
63552 KB |
Output is correct |
11 |
Correct |
718 ms |
52116 KB |
Output is correct |
12 |
Correct |
1372 ms |
60988 KB |
Output is correct |
13 |
Correct |
1337 ms |
58044 KB |
Output is correct |
14 |
Correct |
1373 ms |
60488 KB |
Output is correct |
15 |
Correct |
1411 ms |
60740 KB |
Output is correct |
16 |
Correct |
1347 ms |
60372 KB |
Output is correct |
17 |
Correct |
1326 ms |
60260 KB |
Output is correct |
18 |
Correct |
1296 ms |
61152 KB |
Output is correct |
19 |
Correct |
1385 ms |
62868 KB |
Output is correct |
20 |
Correct |
1417 ms |
60372 KB |
Output is correct |
21 |
Correct |
1405 ms |
60260 KB |
Output is correct |
22 |
Correct |
1433 ms |
60492 KB |
Output is correct |
23 |
Correct |
709 ms |
52068 KB |
Output is correct |
24 |
Correct |
1373 ms |
61212 KB |
Output is correct |
25 |
Correct |
36 ms |
24440 KB |
Output is correct |
26 |
Correct |
23 ms |
22392 KB |
Output is correct |
27 |
Correct |
23 ms |
22396 KB |
Output is correct |
28 |
Correct |
47 ms |
25976 KB |
Output is correct |
29 |
Correct |
34 ms |
24056 KB |
Output is correct |
30 |
Correct |
24 ms |
22492 KB |
Output is correct |
31 |
Correct |
25 ms |
22520 KB |
Output is correct |
32 |
Correct |
26 ms |
22520 KB |
Output is correct |
33 |
Correct |
24 ms |
22520 KB |
Output is correct |
34 |
Correct |
35 ms |
24056 KB |
Output is correct |
35 |
Correct |
24 ms |
22392 KB |
Output is correct |
36 |
Correct |
24 ms |
22392 KB |
Output is correct |
37 |
Correct |
24 ms |
22392 KB |
Output is correct |
38 |
Correct |
24 ms |
22392 KB |
Output is correct |
39 |
Correct |
24 ms |
22392 KB |
Output is correct |
40 |
Correct |
1182 ms |
61364 KB |
Output is correct |
41 |
Correct |
1235 ms |
60772 KB |
Output is correct |
42 |
Correct |
1214 ms |
61068 KB |
Output is correct |
43 |
Correct |
739 ms |
52320 KB |
Output is correct |
44 |
Correct |
772 ms |
52180 KB |
Output is correct |
45 |
Correct |
1346 ms |
64960 KB |
Output is correct |
46 |
Correct |
1317 ms |
64868 KB |
Output is correct |
47 |
Correct |
1337 ms |
63204 KB |
Output is correct |
48 |
Correct |
777 ms |
51644 KB |
Output is correct |
49 |
Correct |
1152 ms |
61556 KB |
Output is correct |
50 |
Correct |
1310 ms |
63868 KB |
Output is correct |
51 |
Correct |
1274 ms |
65508 KB |
Output is correct |