#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ost;
#define endl "\n"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pi pair<int,int>
#define pll pair<long long,long long>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<long long,long long>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vr vector<range<int>>
#define cd complex<double>
#define pb push_back
void frd(string s){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
template<typename T>
struct matrix{
vector<T> mtx;
T Tdef;
int column=-1,row=-1;
matrix() {}
matrix(int r,int c) {
mtx.assign(r*c,Tdef);
row = r;
column = c;
}
matrix(int r,int c,T val){
mtx.assign(r*c,val);
row = r;
column = c;
}
struct proxy{
matrix *m ;
int i;
proxy(matrix* x , int y) : m(x) , i(y){}
T &operator[] (int j){
return (m->mtx[i*(m->row) + j]);
}
};
proxy operator[](int i){
return proxy(this,i);
}
void fill(T x){for(auto &y:mtx)y=x;}
void fill_row(int rw,T x,int l=0,int r=-1){
if(r==-1)r = column-1;
for(int i=l;i<=r;i++){
mtx[rw*row + i] = x;
}
}
void fill_column(int cl,T x,int l=0,int r=-1){
if(r == -1)r = row-1;
for(int i=l;i<=r;i++){
mtx[i*row + cl] = x;
}
}
void inc_row(int rw,T x,int l=0,int r=-1){
if(r==-1)r = column-1;
for(int i=l;i<=r;i++){
mtx[rw*row + i] += x;
}
}
void inc_column(int cl,T x,int l=0,int r=-1){
if(r == -1)r = row-1;
for(int i=l;i<=r;i++){
mtx[i*row + cl] +=x;
}
}
int count(int rw,T x,int l=0,int r=-1){
if(r == -1)r = column-1;
int cnt = 0;
for(int i=l;i<=r;i++)cnt += (mtx[rw*row + i] == x);
return cnt;
}
};
template<typename V,typename S> istream& operator >> (istream &x,pair<V,S> &p){cin >> p.first >> p.second ;return x;}
template<typename V,typename S> ostream& operator << (ostream &x,const pair<V,S> &p){cout << p.first <<" "<<p.second;return x;}
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define abs(x) ((x)>0?(x):-((x)))
#define fr(i,j) for(int i=0;i<j;i++)
#define frt(a,b,c) for(int a=b;a<c;a++)
#define fra(x,y) for(auto &x:y)
#define min(a,b) ((a)<(b)?(a):(b))
#define all(x) x.begin(),x.end()
int mlog(int x) {
return 32 - __builtin_clz(x) - 1;
}
ll sum(ll a,ll b,ll M=1e+9+7){
a%=M;b%=M;return (a+b)%M;
}
ll subs(ll a,ll b,ll M=1e+9+7){
a-=b;a%=M;if(a<0)a+=M;return a;
}
ll mult(ll a,ll b,ll M=1e+9+7){
a%=M;b%=M;return (a*b)%M;
}
ll bp(ll a,ll b,ll M=1e+9+7){
if(b == 0)return 1;
if(b == 1)return a;
ll x = bp(a,b/2,M);
x = mult(x,x,M);
if(b%2)x=mult(x,a,M);
return x;
}
#define int ll
#define MAXN 200005
const ll INF = 1e+16 + 2323231;
vector<vpi> adj;
array<int,MAXN> vis;
array<ll,MAXN> U_dj , V_dj , S_dj , UDP , VDP , DP;
//vll U_dj , V_dj , S_dj;
vvll sp;
void djikstra(array<ll,MAXN> &A,int st){
A[st] = 0;
set<pll> sst;sst.insert({0,st});
while(sst.size()){
auto it = *(sst.begin());
sst.erase(sst.begin());
for(auto &x:adj[it.second]){
if(A[x.first] > A[it.second] + x.second){
sst.erase({A[x.first],x.first});
A[x.first] = A[it.second] + x.second;
sst.insert({A[x.first],x.first});
}
}
}
}
ll ans;
void djikstra2(int V,int en){
fill(all(vis),0);
fill(all(UDP),INF);fill(all(VDP),INF);
fill(all(S_dj),INF);
S_dj[V]=0;
UDP[V] = U_dj[V];VDP[V] = V_dj[V];
set<pll> sst;sst.insert({0,V});
while(sst.size()){
auto it = *(sst.begin());
sst.erase(sst.begin());
for(auto &x:adj[it.second]){
if(S_dj[x.first] == S_dj[it.second] + x.second){
ll MF = min(UDP[it.second],U_dj[x.first]);
ll NF = min(VDP[it.second],V_dj[x.first]);
if(MF + NF < UDP[x.first] + VDP[x.first]){
UDP[x.first] = MF;
VDP[x.first] = NF;
}
}
if(S_dj[x.first] > S_dj[it.second] + x.second){
sst.erase({S_dj[x.first],x.first});
S_dj[x.first] = S_dj[it.second] + x.second;
sst.insert({S_dj[x.first],x.first});
UDP[x.first] = min(UDP[it.second],U_dj[x.first]);
VDP[x.first] = min(VDP[it.second],V_dj[x.first]);
}
}
}
ans = min(ans,VDP[en]+UDP[en]);
}
int32_t main(){
fastio;
int N,M;cin>>N>>M;
adj.assign(N,vpi(0));sp.assign(N,vll(0));
fill(all(vis),0);fill(all(U_dj),INF);fill(all(V_dj),INF);fill(all(S_dj),INF);fill(all(VDP),INF);fill(all(UDP),INF);fill(all(DP),INF);
int S,T,V,U;cin>>S>>T>>V>>U;S--;T--;V--;U--;
fr(i,M){
int a,b;ll c;cin>>a>>b>>c;a--;b--;
adj[a].pb({b,c});
adj[b].pb({a,c});
}
djikstra(U_dj,U);
djikstra(V_dj,V);
ans = V_dj[U];
djikstra2(S,T);
djikstra2(T,S);
cout << ans << endl;
}
Compilation message
commuter_pass.cpp: In function 'void frd(std::string)':
commuter_pass.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
367 ms |
29428 KB |
Output is correct |
2 |
Correct |
302 ms |
28240 KB |
Output is correct |
3 |
Correct |
369 ms |
28344 KB |
Output is correct |
4 |
Correct |
353 ms |
29404 KB |
Output is correct |
5 |
Correct |
257 ms |
28480 KB |
Output is correct |
6 |
Correct |
360 ms |
29264 KB |
Output is correct |
7 |
Correct |
287 ms |
28168 KB |
Output is correct |
8 |
Correct |
327 ms |
28772 KB |
Output is correct |
9 |
Correct |
292 ms |
28244 KB |
Output is correct |
10 |
Correct |
291 ms |
28700 KB |
Output is correct |
11 |
Correct |
72 ms |
21356 KB |
Output is correct |
12 |
Correct |
301 ms |
28312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
379 ms |
28956 KB |
Output is correct |
2 |
Correct |
315 ms |
28080 KB |
Output is correct |
3 |
Correct |
343 ms |
28240 KB |
Output is correct |
4 |
Correct |
330 ms |
28236 KB |
Output is correct |
5 |
Correct |
377 ms |
28356 KB |
Output is correct |
6 |
Correct |
280 ms |
28240 KB |
Output is correct |
7 |
Correct |
350 ms |
28232 KB |
Output is correct |
8 |
Correct |
356 ms |
28248 KB |
Output is correct |
9 |
Correct |
328 ms |
28060 KB |
Output is correct |
10 |
Correct |
347 ms |
27996 KB |
Output is correct |
11 |
Correct |
77 ms |
21360 KB |
Output is correct |
12 |
Correct |
343 ms |
28364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
12636 KB |
Output is correct |
2 |
Correct |
2 ms |
11356 KB |
Output is correct |
3 |
Correct |
3 ms |
11436 KB |
Output is correct |
4 |
Correct |
12 ms |
14084 KB |
Output is correct |
5 |
Correct |
7 ms |
12636 KB |
Output is correct |
6 |
Correct |
3 ms |
11356 KB |
Output is correct |
7 |
Correct |
3 ms |
11356 KB |
Output is correct |
8 |
Correct |
4 ms |
11612 KB |
Output is correct |
9 |
Correct |
3 ms |
11524 KB |
Output is correct |
10 |
Correct |
8 ms |
13148 KB |
Output is correct |
11 |
Correct |
3 ms |
11284 KB |
Output is correct |
12 |
Correct |
2 ms |
11356 KB |
Output is correct |
13 |
Correct |
2 ms |
11356 KB |
Output is correct |
14 |
Correct |
3 ms |
11356 KB |
Output is correct |
15 |
Correct |
3 ms |
11288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
367 ms |
29428 KB |
Output is correct |
2 |
Correct |
302 ms |
28240 KB |
Output is correct |
3 |
Correct |
369 ms |
28344 KB |
Output is correct |
4 |
Correct |
353 ms |
29404 KB |
Output is correct |
5 |
Correct |
257 ms |
28480 KB |
Output is correct |
6 |
Correct |
360 ms |
29264 KB |
Output is correct |
7 |
Correct |
287 ms |
28168 KB |
Output is correct |
8 |
Correct |
327 ms |
28772 KB |
Output is correct |
9 |
Correct |
292 ms |
28244 KB |
Output is correct |
10 |
Correct |
291 ms |
28700 KB |
Output is correct |
11 |
Correct |
72 ms |
21356 KB |
Output is correct |
12 |
Correct |
301 ms |
28312 KB |
Output is correct |
13 |
Correct |
379 ms |
28956 KB |
Output is correct |
14 |
Correct |
315 ms |
28080 KB |
Output is correct |
15 |
Correct |
343 ms |
28240 KB |
Output is correct |
16 |
Correct |
330 ms |
28236 KB |
Output is correct |
17 |
Correct |
377 ms |
28356 KB |
Output is correct |
18 |
Correct |
280 ms |
28240 KB |
Output is correct |
19 |
Correct |
350 ms |
28232 KB |
Output is correct |
20 |
Correct |
356 ms |
28248 KB |
Output is correct |
21 |
Correct |
328 ms |
28060 KB |
Output is correct |
22 |
Correct |
347 ms |
27996 KB |
Output is correct |
23 |
Correct |
77 ms |
21360 KB |
Output is correct |
24 |
Correct |
343 ms |
28364 KB |
Output is correct |
25 |
Correct |
8 ms |
12636 KB |
Output is correct |
26 |
Correct |
2 ms |
11356 KB |
Output is correct |
27 |
Correct |
3 ms |
11436 KB |
Output is correct |
28 |
Correct |
12 ms |
14084 KB |
Output is correct |
29 |
Correct |
7 ms |
12636 KB |
Output is correct |
30 |
Correct |
3 ms |
11356 KB |
Output is correct |
31 |
Correct |
3 ms |
11356 KB |
Output is correct |
32 |
Correct |
4 ms |
11612 KB |
Output is correct |
33 |
Correct |
3 ms |
11524 KB |
Output is correct |
34 |
Correct |
8 ms |
13148 KB |
Output is correct |
35 |
Correct |
3 ms |
11284 KB |
Output is correct |
36 |
Correct |
2 ms |
11356 KB |
Output is correct |
37 |
Correct |
2 ms |
11356 KB |
Output is correct |
38 |
Correct |
3 ms |
11356 KB |
Output is correct |
39 |
Correct |
3 ms |
11288 KB |
Output is correct |
40 |
Correct |
331 ms |
35780 KB |
Output is correct |
41 |
Correct |
333 ms |
33104 KB |
Output is correct |
42 |
Correct |
363 ms |
32852 KB |
Output is correct |
43 |
Correct |
83 ms |
23380 KB |
Output is correct |
44 |
Correct |
79 ms |
23480 KB |
Output is correct |
45 |
Correct |
225 ms |
31576 KB |
Output is correct |
46 |
Correct |
261 ms |
31412 KB |
Output is correct |
47 |
Correct |
334 ms |
33132 KB |
Output is correct |
48 |
Correct |
84 ms |
22824 KB |
Output is correct |
49 |
Correct |
302 ms |
35328 KB |
Output is correct |
50 |
Correct |
276 ms |
31896 KB |
Output is correct |
51 |
Correct |
253 ms |
31572 KB |
Output is correct |