oj.uz

Submission #945530

# Submission time Handle Problem Language Result Execution time Memory
945530 2024-03-14T03:37:45 Z Xiaoyang Commuter Pass (JOI18_commuter_pass) C++17
16 / 100
 305 ms 24516 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
 
#define fi first 
#define se second 
#define pll pair<ll,ll>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define MP make_pair
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define endl "\n"
const ll inf=1e18;
ll lowbit(ll x){return x&(-x);}


const ll maxn=1e5+5;
vector<pll>alist[maxn];
ll ds[maxn],dt[maxn],du[maxn],dv[maxn];

void dijkstra(ll st,ll dist[]){
	rep(i,0,maxn)dist[i]=inf;
	priority_queue<pll,vector<pll>,greater<pll>>s;
	s.push(MP(0ll,st));
	dist[st]=0;
	
	while(!s.empty()){
		auto u=s.top();
		s.pop();
		if(u.fi!=dist[u.se])continue;
		for(auto x:alist[u.se]){
			if(x.fi+u.fi<dist[x.se]){
				dist[x.se]=x.fi+u.fi;
				s.push(MP(dist[x.se],x.se));
			}
		}
	}
	
}

ll f[maxn],ff[maxn];
ll n,m;
ll t; 

void dijk(ll orig[],ll dist[]){
	priority_queue<pll,vector<pll>,greater<pll>>s;
	rep(i,1,n+1){
		dist[i]=orig[i];
		s.push(MP(orig[i],i));
	}
	while(!s.empty()){
		auto u=s.top();
		s.pop();
		if(u.fi!=dist[u.se])continue;
		for(auto x:alist[u.se]){
			//the edge is on the path from s to t => free
			if(ds[x.se]+x.fi+dt[u.se]==ds[t] and dist[u.se]<dist[x.se]){
				dist[x.se]=dist[u.se];
				s.push(MP(dist[x.se],x.se));
			}
		}
	}
}

ll s;
ll u,v;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	cin>>s>>t;
	cin>>u>>v;
	rep(i,0,m){
		ll a,b,c;cin>>a>>b>>c;
		alist[a].pb(MP(c,b));
		alist[b].pb(MP(c,a));
	}
	
	dijkstra(s,ds);
	dijkstra(t,dt);
	dijkstra(u,du);
	dijkstra(v,dv);
	
	dijk(dv,f);
	dijk(du,ff);
	ll ans=inf;
	
	rep(i,1,n+1){
		ans=min(ans,du[i]+f[i]);	
		//ans=min(ans,dv[i]+ff[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 21736 KB Output is correct
2 Correct 260 ms 21456 KB Output is correct
3 Correct 232 ms 21348 KB Output is correct
4 Correct 255 ms 21452 KB Output is correct
5 Correct 255 ms 21324 KB Output is correct
6 Correct 254 ms 21664 KB Output is correct
7 Correct 227 ms 21408 KB Output is correct
8 Correct 251 ms 21868 KB Output is correct
9 Correct 247 ms 21536 KB Output is correct
10 Correct 185 ms 21480 KB Output is correct
11 Correct 109 ms 16360 KB Output is correct
12 Correct 255 ms 21376 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 21380 KB Output is correct
2 Correct 261 ms 21664 KB Output is correct
3 Correct 253 ms 24516 KB Output is correct
4 Incorrect 262 ms 24364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 21736 KB Output is correct
2 Correct 260 ms 21456 KB Output is correct
3 Correct 232 ms 21348 KB Output is correct
4 Correct 255 ms 21452 KB Output is correct
5 Correct 255 ms 21324 KB Output is correct
6 Correct 254 ms 21664 KB Output is correct
7 Correct 227 ms 21408 KB Output is correct
8 Correct 251 ms 21868 KB Output is correct
9 Correct 247 ms 21536 KB Output is correct
10 Correct 185 ms 21480 KB Output is correct
11 Correct 109 ms 16360 KB Output is correct
12 Correct 255 ms 21376 KB Output is correct
13 Correct 305 ms 21380 KB Output is correct
14 Correct 261 ms 21664 KB Output is correct
15 Correct 253 ms 24516 KB Output is correct
16 Incorrect 262 ms 24364 KB Output isn't correct
17 Halted 0 ms 0 KB -