Submission #961213

#	Time	Username	Problem	Language	Result	Execution time	Memory
961213		LCJLY	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	367 ms	32436 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;

vector<pii>adj[100005];

void solve(){
	int n,m;
	cin >> n >> m;
	int a,b;
	cin >> a >> b;
	int s,t;
	cin >> s >> t;
	
	int temp,temp2,temp3;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2 >> temp3;
		adj[temp].push_back({temp2,temp3});
		adj[temp2].push_back({temp,temp3});
	}
	
	int dist[n+5]; //a
	int dist2[n+5]; //b
	memset(dist,-1,sizeof(dist));
	memset(dist2,-1,sizeof(dist2));
	
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	dist[a]=0;
	pq.push({0,a});
	
	while(!pq.empty()){
		pii cur=pq.top();
		pq.pop();
		int index=cur.second;
		int d=cur.first;
		if(dist[index]!=d) continue;
		for(auto it:adj[index]){
			int nx=it.first;
			int nd=d+it.second;
			if(dist[nx]!=-1&&dist[nx]<=nd) continue;
			dist[nx]=nd;
			pq.push({nd,nx});
		}
	}
	
	dist2[b]=0;
	pq.push({0,b});
	while(!pq.empty()){
		pii cur=pq.top();
		pq.pop();
		int index=cur.second;
		int d=cur.first;
		if(dist2[index]!=d) continue;
		for(auto it:adj[index]){
			int nx=it.first;
			int nd=d+it.second;
			if(dist2[nx]!=-1&&dist2[nx]<=nd) continue;
			dist2[nx]=nd;
			pq.push({nd,nx});
		}
	}
	
	priority_queue<pi2,vector<pi2>,greater<pi2>>pq2;
	int dist3[n+5][5];
	memset(dist3,-1,sizeof(dist3));
	dist3[s][0]=0;
	pq2.push({0,{s,0}});
	
	int target=dist[b];
	
	while(!pq2.empty()){
		pi2 cur=pq2.top();
		pq2.pop();
		int index=cur.second.first;
		int k=cur.second.second;
		int d=cur.first;
		//show3(index,index,k,k,d,d);
		for(auto it:adj[index]){
			int nx=it.first;
			int path=0;
			if(dist[index]+it.second+dist2[nx]==target) path=1;
			if(dist[nx]+it.second+dist2[index]==target) path=2;
			
			if(k==0){
				if( !(dist3[nx][k]!=-1&&dist3[nx][k]<=d+it.second) ){
					dist3[nx][k]=d+it.second;
					pq2.push({d+it.second,{nx,k}});
				}
				
				if( !(dist3[nx][path]!=-1&&dist3[nx][path]<=d) && (path!=0) ){
					dist3[nx][path]=d;
					pq2.push({d,{nx,path}});
				}
			}
			else if(k==1||k==2){
				if(path==k){
					if( !(dist3[nx][path]!=-1&&dist3[nx][path]<=d) ){
						dist3[nx][path]=d;
						pq2.push({d,{nx,path}});
					}
				}
				else{
					if( !(dist3[nx][3]!=-1&&dist3[nx][3]<=d+it.second) ){
						dist3[nx][3]=d+it.second;
						pq2.push({d+it.second,{nx,3}});
					}
				}
			}
			else if(k==3){
				if( !(dist3[nx][k]!=-1&&dist3[nx][k]<=d+it.second) ){
					dist3[nx][k]=d+it.second;
					pq2.push({d+it.second,{nx,k}});
				}
			}
		}	
	}
	
	int best=1e18;
	for(int x=0;x<4;x++){
		if(dist3[t][x]==-1) continue;
		best=min(best,dist3[t][x]);
	}
	cout << best;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45