Submission #754219

#	Time	Username	Problem	Language	Result	Execution time	Memory
754219		jamielim	Commuter Pass (JOI18_commuter_pass)	C++14	40 / 100	507 ms	20020 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const ll LLINF=1012345678012345678LL;

int n,m;
int s,t,u,v;
vector<ii> adj[100005];
ll dist[4][100005];
ll minsofar[100005];

void dijkstra(int idx,int source){
	for(int i=0;i<n;i++)dist[idx][i]=LLINF;
	dist[idx][source]=0;
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
	pq.push(mp(0,source));
	while(!pq.empty()){
		pair<ll,int> cur=pq.top();pq.pop();
		for(ii i:adj[cur.se]){
			if(dist[idx][i.fi]>dist[idx][cur.se]+i.se){
				dist[idx][i.fi]=dist[idx][cur.se]+i.se;
				pq.push(mp(dist[idx][i.fi],i.fi));
			}
		}
	}
}

int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);s--;t--;u--;v--;
	int a,b,c;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&a,&b,&c);a--;b--;
		adj[a].pb(b,c);
		adj[b].pb(a,c);
	}
	dijkstra(0,u);dijkstra(1,v);dijkstra(2,s);
	ll ans=LLINF;
	for(int i=0;i<n;i++){
		dist[3][i]=LLINF;
		minsofar[i]=dist[0][i];
	}
	dist[3][t]=0;
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
	pq.push(mp(0,t));
	int idx=3;
	while(!pq.empty()){
		pair<ll,int> cur=pq.top();pq.pop();
		for(ii i:adj[cur.se]){
			if(dist[idx][i.fi]>dist[idx][cur.se]+i.se){
				dist[idx][i.fi]=dist[idx][cur.se]+i.se;
				minsofar[i.fi]=min(minsofar[cur.se],minsofar[i.fi]);
				pq.push(mp(dist[idx][i.fi],i.fi));
			}else if(dist[idx][i.fi]==dist[idx][cur.se]+i.se){
				minsofar[i.fi]=min(minsofar[cur.se],minsofar[i.fi]);
			}
		}
	}
	for(int i=0;i<n;i++){
		if(dist[2][i]+dist[3][i]==dist[2][t])ans=min(ans,minsofar[i]+dist[1][i]);
	}
	for(int i=0;i<n;i++){
		dist[2][i]=LLINF;
		minsofar[i]=dist[0][i];
	}
	dist[2][s]=0;
	pq.push(mp(0,s));
	idx=2;
	while(!pq.empty()){
		pair<ll,int> cur=pq.top();pq.pop();
		for(ii i:adj[cur.se]){
			if(dist[idx][i.fi]>dist[idx][cur.se]+i.se){
				dist[idx][i.fi]=dist[idx][cur.se]+i.se;
				minsofar[i.fi]=min(minsofar[cur.se],minsofar[i.fi]);
				pq.push(mp(dist[idx][i.fi],i.fi));
			}else if(dist[idx][i.fi]==dist[idx][cur.se]+i.se){
				minsofar[i.fi]=min(minsofar[cur.se],minsofar[i.fi]);
			}
		}
	}
	for(int i=0;i<n;i++){
		if(dist[2][i]+dist[3][i]==dist[2][t])ans=min(ans,minsofar[i]+dist[1][i]);
	}
	printf("%lld",min(ans,dist[0][v]));
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);s--;t--;u--;v--;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d%d",&a,&b,&c);a--;b--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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