Submission #729697

#	Time	Username	Problem	Language	Result	Execution time	Memory
729697		pcc	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	359 ms	26400 KiB

commuter_pass

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

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 1e5+10;
const ll inf = 1e18;
vector<pll> paths[mxn];
ll dist1[mxn],dist2[mxn],dist3[mxn],deg[mxn];
vector<int> dag[mxn];
bitset<mxn> done;
ll dp[2][mxn];
int n,m;
int s,e,u,v;
ll ans = 1e18;

void dijkstra(int st,ll dist[]){
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	fill(dist,dist+n+1,inf);
	dist[st] = 0;
	pq.push(make_pair(0,st));
	while(!pq.empty()){
		auto now = pq.top().sc;
		auto val = pq.top().fs;
		pq.pop();
		//cout<<now<<endl;
		if(val != dist[now])continue;
		for(auto nxt:paths[now]){
			if(dist[nxt.fs]>dist[now]+nxt.sc){
				dist[nxt.fs] = dist[now]+nxt.sc;
				pq.push(make_pair(dist[nxt.fs],nxt.fs));
			}
		}
	}
	return;
}

void solve(){
	cin>>n>>m;
	cin>>s>>e>>u>>v;
	fill(dp[0],dp[0]+mxn,inf);
	fill(dp[1],dp[1]+mxn,inf);
	for(int i = 0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		paths[a].push_back(make_pair(b,c));
		paths[b].push_back(make_pair(a,c));
	}
	dijkstra(s,dist1);
	dijkstra(u,dist2);
	dijkstra(v,dist3);
	queue<int> q;
	q.push(e);
	done[e] = true;
	//for(int i = 1;i<=n;i++)cout<<dist1[i]<<' ';cout<<endl;
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		for(auto nxt:paths[now]){
			//cout<<nxt.fs<<":"<<now<<endl;
			if(dist1[nxt.fs] + nxt.sc == dist1[now]){
				if(!done[nxt.fs])q.push(nxt.fs);
				done[nxt.fs] = true;
				dag[now].push_back(nxt.fs);
				deg[nxt.fs]++;
			}
		}
	}
	q.push(e);
	/*
	for(int i = 1;i<=n;i++){
		for(auto nxt:dag[i])cout<<i<<','<<nxt<<endl;
	}

   */
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		dp[0][now] = min(dp[0][now],dist2[now]);
		dp[1][now] = min(dp[1][now],dist3[now]);
		ans = min({ans,dp[0][now]+dist3[now],dp[1][now]+dist2[now]});
		for(auto nxt:dag[now]){
			deg[nxt]--;
			if(!deg[nxt])q.push(nxt);
			dp[0][nxt] = min(dp[0][nxt],dp[0][now]);
			dp[1][nxt] = min(dp[1][nxt],dp[1][now]);
		}
	}
	cout<<min(ans,dist2[v]);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	while(t--)solve();
}

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