#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ld,ld> id;
typedef tuple<ll,ll,ll> tl;
typedef tuple<ll,ll,ll,ll> ql;
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define ROF(i, a, b) for(ll i=(a); i>=(b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define FILL(x, n, v) fill(x, x+n, v);
#define ALL(x) x.begin(), x.end()
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f first
#define s second
#define ins insert
#define e emplace
#define eb emplace_back
#define ef emplace_front
#define p push
#define pf push_front
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ft front
#define bk back
#define pp pop
#define ppb pop_back
#define ppf pop_front
#define db cout<<"YEET\n";
#define ct(x) cout<<x<<'\n';
const ll MOD = 1e9+7; //998244353
const ll MAXN = 1e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
int main(){
FAST
ll n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
ll dist1[MAXN], dist2[MAXN];
vector<ii> adjlist[MAXN];
FOR(i,1,n) dist1[i] = dist2[i] = INF;
dist1[u] = dist2[v] = 0;
FOR(i,1,m){
ll a, b, c;
cin >> a >> b >> c;
adjlist[a].eb(b,c);
adjlist[b].eb(a,c);
}
priority_queue<ii, vector<ii>, greater<ii> > pq;
pq.e(0,u);
while (!pq.empty()){
ll dist = pq.top().f;
ll u = pq.top().s;
pq.pp();
if (dist > dist1[u]) continue;
for (auto edge : adjlist[u]){
ll v = edge.f;
ll cost = edge.s;
if (dist1[u] + cost < dist1[v]){
dist1[v] = dist1[u] + cost;
pq.e(dist1[v], v);
}
}
}
pq.e(0,v);
while (!pq.empty()){
ll dist = pq.top().f;
ll u = pq.top().s;
pq.pp();
if (dist > dist2[u]) continue;
for (auto edge : adjlist[u]){
ll v = edge.f;
ll cost = edge.s;
if (dist2[u] + cost < dist2[v]){
dist2[v] = dist2[u] + cost;
pq.e(dist2[v], v);
}
}
}
ii minuv[MAXN];
ll mindist[MAXN];
FOR(i,1,n) minuv[i] = mp(INF,INF), mindist[i] = INF;
minuv[s] = mp(dist1[s], dist2[s]);
mindist[s] = 0;
pq.e(0,s);
while (!pq.empty()){
ll dist = pq.top().f;
ll u = pq.top().s;
pq.pp();
if (dist > mindist[u]) continue;
for (auto edge : adjlist[u]){
ll v = edge.f;
ll cost = edge.s;
if (mindist[u] + cost < mindist[v]){
mindist[v] = mindist[u] + cost;
minuv[v] = mp(min(dist1[v], minuv[u].f), min(dist2[v], minuv[u].s));
pq.e(mindist[v], v);
} else if (mindist[u] + cost == mindist[v]){
ll chk1 = min(dist1[v], minuv[u].f) + min(dist2[v], minuv[u].s);
ll chk2 = minuv[v].f + minuv[v].s;
if (chk1 < chk2) minuv[v] = mp(min(dist1[v], minuv[u].f), min(dist2[v], minuv[u].s));
}
}
}
cout << min(minuv[t].f+minuv[t].s, dist1[v]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
287 ms |
19940 KB |
Output is correct |
2 |
Correct |
300 ms |
19820 KB |
Output is correct |
3 |
Correct |
323 ms |
19564 KB |
Output is correct |
4 |
Correct |
306 ms |
19940 KB |
Output is correct |
5 |
Correct |
277 ms |
19692 KB |
Output is correct |
6 |
Correct |
304 ms |
20132 KB |
Output is correct |
7 |
Correct |
300 ms |
19824 KB |
Output is correct |
8 |
Correct |
302 ms |
19948 KB |
Output is correct |
9 |
Correct |
314 ms |
19668 KB |
Output is correct |
10 |
Correct |
263 ms |
19564 KB |
Output is correct |
11 |
Correct |
134 ms |
13688 KB |
Output is correct |
12 |
Correct |
307 ms |
19692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
309 ms |
19948 KB |
Output is correct |
2 |
Correct |
333 ms |
19824 KB |
Output is correct |
3 |
Correct |
322 ms |
19816 KB |
Output is correct |
4 |
Correct |
329 ms |
19824 KB |
Output is correct |
5 |
Correct |
316 ms |
19820 KB |
Output is correct |
6 |
Correct |
313 ms |
19696 KB |
Output is correct |
7 |
Correct |
295 ms |
19692 KB |
Output is correct |
8 |
Correct |
311 ms |
19820 KB |
Output is correct |
9 |
Correct |
315 ms |
19820 KB |
Output is correct |
10 |
Correct |
316 ms |
19824 KB |
Output is correct |
11 |
Correct |
122 ms |
13688 KB |
Output is correct |
12 |
Correct |
304 ms |
19688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
5632 KB |
Output is correct |
2 |
Correct |
7 ms |
4352 KB |
Output is correct |
3 |
Correct |
7 ms |
4352 KB |
Output is correct |
4 |
Correct |
22 ms |
6912 KB |
Output is correct |
5 |
Correct |
14 ms |
5632 KB |
Output is correct |
6 |
Correct |
7 ms |
4352 KB |
Output is correct |
7 |
Correct |
7 ms |
4352 KB |
Output is correct |
8 |
Correct |
8 ms |
4480 KB |
Output is correct |
9 |
Correct |
7 ms |
4352 KB |
Output is correct |
10 |
Correct |
14 ms |
5632 KB |
Output is correct |
11 |
Correct |
7 ms |
4224 KB |
Output is correct |
12 |
Correct |
7 ms |
4352 KB |
Output is correct |
13 |
Correct |
7 ms |
4352 KB |
Output is correct |
14 |
Correct |
7 ms |
4352 KB |
Output is correct |
15 |
Correct |
8 ms |
4352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
287 ms |
19940 KB |
Output is correct |
2 |
Correct |
300 ms |
19820 KB |
Output is correct |
3 |
Correct |
323 ms |
19564 KB |
Output is correct |
4 |
Correct |
306 ms |
19940 KB |
Output is correct |
5 |
Correct |
277 ms |
19692 KB |
Output is correct |
6 |
Correct |
304 ms |
20132 KB |
Output is correct |
7 |
Correct |
300 ms |
19824 KB |
Output is correct |
8 |
Correct |
302 ms |
19948 KB |
Output is correct |
9 |
Correct |
314 ms |
19668 KB |
Output is correct |
10 |
Correct |
263 ms |
19564 KB |
Output is correct |
11 |
Correct |
134 ms |
13688 KB |
Output is correct |
12 |
Correct |
307 ms |
19692 KB |
Output is correct |
13 |
Correct |
309 ms |
19948 KB |
Output is correct |
14 |
Correct |
333 ms |
19824 KB |
Output is correct |
15 |
Correct |
322 ms |
19816 KB |
Output is correct |
16 |
Correct |
329 ms |
19824 KB |
Output is correct |
17 |
Correct |
316 ms |
19820 KB |
Output is correct |
18 |
Correct |
313 ms |
19696 KB |
Output is correct |
19 |
Correct |
295 ms |
19692 KB |
Output is correct |
20 |
Correct |
311 ms |
19820 KB |
Output is correct |
21 |
Correct |
315 ms |
19820 KB |
Output is correct |
22 |
Correct |
316 ms |
19824 KB |
Output is correct |
23 |
Correct |
122 ms |
13688 KB |
Output is correct |
24 |
Correct |
304 ms |
19688 KB |
Output is correct |
25 |
Correct |
15 ms |
5632 KB |
Output is correct |
26 |
Correct |
7 ms |
4352 KB |
Output is correct |
27 |
Correct |
7 ms |
4352 KB |
Output is correct |
28 |
Correct |
22 ms |
6912 KB |
Output is correct |
29 |
Correct |
14 ms |
5632 KB |
Output is correct |
30 |
Correct |
7 ms |
4352 KB |
Output is correct |
31 |
Correct |
7 ms |
4352 KB |
Output is correct |
32 |
Correct |
8 ms |
4480 KB |
Output is correct |
33 |
Correct |
7 ms |
4352 KB |
Output is correct |
34 |
Correct |
14 ms |
5632 KB |
Output is correct |
35 |
Correct |
7 ms |
4224 KB |
Output is correct |
36 |
Correct |
7 ms |
4352 KB |
Output is correct |
37 |
Correct |
7 ms |
4352 KB |
Output is correct |
38 |
Correct |
7 ms |
4352 KB |
Output is correct |
39 |
Correct |
8 ms |
4352 KB |
Output is correct |
40 |
Correct |
286 ms |
21988 KB |
Output is correct |
41 |
Correct |
287 ms |
22124 KB |
Output is correct |
42 |
Correct |
300 ms |
22384 KB |
Output is correct |
43 |
Correct |
134 ms |
13944 KB |
Output is correct |
44 |
Correct |
119 ms |
13944 KB |
Output is correct |
45 |
Correct |
292 ms |
21216 KB |
Output is correct |
46 |
Correct |
267 ms |
20844 KB |
Output is correct |
47 |
Correct |
301 ms |
22008 KB |
Output is correct |
48 |
Correct |
136 ms |
13432 KB |
Output is correct |
49 |
Correct |
239 ms |
21600 KB |
Output is correct |
50 |
Correct |
284 ms |
21364 KB |
Output is correct |
51 |
Correct |
301 ms |
20972 KB |
Output is correct |