#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";};
template<class A, class B> ostream& operator<<(ostream &cout, const pair<A,B> &x) {return cout << "(" <<x.first << ", " << x.second << ")";};
template<class T> void pv(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) cerr << *i << " "; cerr << "]\n";}
void _print() {cerr << "]\n";}
template<class T, class... V> void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = [", _print(x)
#define fi first
#define se second
#define SZ(x) (int)((x).size())
#define pii pair<int,int>
const int mx = 1e5+5;
const ll inf = 1e17; //change
template<class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<class T> void dijkstra(const vector<vector<pair<int,T>>>& adj, vector<T>& dist, int src) {
fill(dist.begin(), dist.end(), inf);
dist[src] = 0;
vector<bool> visited(SZ(dist));
minpq<pair<T,int>> pq;
pq.push({0,src});
while (SZ(pq)) {
pair<ll,int> t = pq.top();
pq.pop();
if (visited[t.se]) continue;
visited[t.se] = true;
for (pair<int,T> p : adj[t.se]) {
if (dist[t.se]+p.se < dist[p.fi]) {
dist[p.fi] = dist[t.se]+p.se;
pq.push({dist[p.fi], p.fi});
}
}
}
}
template<class T> void uni(vector<T> &a) {
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
int s,t,u,v;
cin >> s >> t >> u >> v;
vector<array<ll,3>> edges;
vector<vector<pair<int,ll>>> adj(n+1);
for (int q = 0; q < m; q++) {
ll a,b,c;
cin >> a >> b >> c;
adj[a].emplace_back(b,c);
adj[b].emplace_back(a,c);
edges.push_back({a,b,c});
}
vector<ll> sdist(n+1), tdist(n+1), udist(n+1), vdist(n+1);
dijkstra(adj,sdist,s);
dijkstra(adj,tdist,t);
dijkstra(adj,udist,u);
dijkstra(adj,vdist,v);
vector<pair<ll,int>> on;
vector<set<pair<int,ll>>> adj2(n+1);
for (array<ll,3> e : edges) {
bool zero = false;
if (sdist[e[0]]+e[2]+tdist[e[1]] == sdist[t]) zero = true;
if (sdist[e[1]]+e[2]+tdist[e[0]] == sdist[t]) zero = true;
if (zero) {
on.emplace_back(udist[e[0]],e[0]);
on.emplace_back(udist[e[1]],e[1]);
adj2[e[0]].insert({e[1],e[2]});
adj2[e[1]].insert({e[0],e[2]});
}
}
uni(on);
ll ans = udist[v];
for (int q = 0; q < SZ(on); q++) {
ll d = on[q].fi, x = on[q].se;
queue<pair<ll,int>> bfs;
bfs.push({0,x});
while (SZ(bfs)) {
pair<ll,int> f = bfs.front();
bfs.pop();
ans = min(ans, d+vdist[f.se]);
auto it = adj2[f.se].begin();
while (it != adj2[f.se].end()) {
auto it1 = it++;
bool onpath = false;
if (it1->se + f.fi+sdist[x]+tdist[it1->fi] == sdist[t]) onpath = true;
if (it1->se + f.fi+sdist[it1->fi]+tdist[x] == sdist[t]) onpath = true;
if (onpath) {
bfs.push({f.fi+it1->se, it1->fi});
adj2[f.se].erase(it1);
}
}
}
}
cout << ans << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
379 ms |
29576 KB |
Output is correct |
2 |
Correct |
433 ms |
32372 KB |
Output is correct |
3 |
Correct |
424 ms |
38548 KB |
Output is correct |
4 |
Correct |
313 ms |
29632 KB |
Output is correct |
5 |
Correct |
420 ms |
38584 KB |
Output is correct |
6 |
Correct |
364 ms |
29672 KB |
Output is correct |
7 |
Correct |
436 ms |
38592 KB |
Output is correct |
8 |
Correct |
436 ms |
35464 KB |
Output is correct |
9 |
Correct |
334 ms |
28296 KB |
Output is correct |
10 |
Correct |
287 ms |
28300 KB |
Output is correct |
11 |
Correct |
178 ms |
25520 KB |
Output is correct |
12 |
Correct |
374 ms |
28252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
412 ms |
30440 KB |
Output is correct |
2 |
Correct |
414 ms |
31188 KB |
Output is correct |
3 |
Correct |
384 ms |
30228 KB |
Output is correct |
4 |
Correct |
436 ms |
30916 KB |
Output is correct |
5 |
Correct |
447 ms |
32376 KB |
Output is correct |
6 |
Correct |
427 ms |
35540 KB |
Output is correct |
7 |
Correct |
482 ms |
38520 KB |
Output is correct |
8 |
Correct |
394 ms |
31208 KB |
Output is correct |
9 |
Correct |
455 ms |
32444 KB |
Output is correct |
10 |
Correct |
400 ms |
30440 KB |
Output is correct |
11 |
Correct |
227 ms |
28692 KB |
Output is correct |
12 |
Correct |
439 ms |
36204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
4104 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
18 ms |
4728 KB |
Output is correct |
5 |
Correct |
10 ms |
2436 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
9 ms |
2436 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
379 ms |
29576 KB |
Output is correct |
2 |
Correct |
433 ms |
32372 KB |
Output is correct |
3 |
Correct |
424 ms |
38548 KB |
Output is correct |
4 |
Correct |
313 ms |
29632 KB |
Output is correct |
5 |
Correct |
420 ms |
38584 KB |
Output is correct |
6 |
Correct |
364 ms |
29672 KB |
Output is correct |
7 |
Correct |
436 ms |
38592 KB |
Output is correct |
8 |
Correct |
436 ms |
35464 KB |
Output is correct |
9 |
Correct |
334 ms |
28296 KB |
Output is correct |
10 |
Correct |
287 ms |
28300 KB |
Output is correct |
11 |
Correct |
178 ms |
25520 KB |
Output is correct |
12 |
Correct |
374 ms |
28252 KB |
Output is correct |
13 |
Correct |
412 ms |
30440 KB |
Output is correct |
14 |
Correct |
414 ms |
31188 KB |
Output is correct |
15 |
Correct |
384 ms |
30228 KB |
Output is correct |
16 |
Correct |
436 ms |
30916 KB |
Output is correct |
17 |
Correct |
447 ms |
32376 KB |
Output is correct |
18 |
Correct |
427 ms |
35540 KB |
Output is correct |
19 |
Correct |
482 ms |
38520 KB |
Output is correct |
20 |
Correct |
394 ms |
31208 KB |
Output is correct |
21 |
Correct |
455 ms |
32444 KB |
Output is correct |
22 |
Correct |
400 ms |
30440 KB |
Output is correct |
23 |
Correct |
227 ms |
28692 KB |
Output is correct |
24 |
Correct |
439 ms |
36204 KB |
Output is correct |
25 |
Correct |
30 ms |
4104 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
18 ms |
4728 KB |
Output is correct |
29 |
Correct |
10 ms |
2436 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
588 KB |
Output is correct |
32 |
Correct |
2 ms |
588 KB |
Output is correct |
33 |
Correct |
2 ms |
460 KB |
Output is correct |
34 |
Correct |
9 ms |
2436 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
348 ms |
29060 KB |
Output is correct |
41 |
Correct |
343 ms |
28156 KB |
Output is correct |
42 |
Correct |
351 ms |
28320 KB |
Output is correct |
43 |
Correct |
289 ms |
34408 KB |
Output is correct |
44 |
Correct |
309 ms |
34396 KB |
Output is correct |
45 |
Correct |
773 ms |
57384 KB |
Output is correct |
46 |
Correct |
760 ms |
57492 KB |
Output is correct |
47 |
Correct |
354 ms |
29412 KB |
Output is correct |
48 |
Correct |
299 ms |
34628 KB |
Output is correct |
49 |
Correct |
294 ms |
29024 KB |
Output is correct |
50 |
Correct |
646 ms |
50584 KB |
Output is correct |
51 |
Correct |
762 ms |
57556 KB |
Output is correct |