Submission #729402

#	Time	Username	Problem	Language	Result	Execution time	Memory
729402		pcc	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	496 ms	28656 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 = 2e5+10;
const ll inf = 1e18;
vector<pll> paths[mxn];
ll dist[mxn];
ll dist2[mxn];
ll dist3[mxn];
bitset<mxn> done;
ll n,m;
ll s,e,u,v;


void solve(){
	cin>>n>>m;
	cin>>s>>e>>u>>v;
	for(int i = 0;i<m;i++){
		ll a,b,c;
		cin>>a>>b>>c;
		paths[a].push_back(make_pair(b,c));
		paths[b].push_back(make_pair(a,c));
	}
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	fill(dist,dist+n+1,inf);
	fill(dist2,dist2+n+1,inf);
	fill(dist3,dist3+n+1,inf);

	dist[s] = 0;
	pq.push(make_pair(0LL,s));
	while(!pq.empty()){
		auto now = pq.top().sc;
		pq.pop();
		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));
			}
		}
	}


	dist3[e] = 0;
	pq.push(make_pair(0LL,e));
	while(!pq.empty()){
		auto now = pq.top().sc;
		pq.pop();
		for(auto nxt:paths[now]){
			if(dist3[nxt.fs]>dist3[now]+nxt.sc){
				dist3[nxt.fs] = dist3[now]+nxt.sc;
				pq.push(make_pair(dist3[nxt.fs],nxt.fs));
			}
		}
	}

	//for(int i = 1;i<=n;i++)cout<<dist[i]<<' ';cout<<endl;
	//for(int i = 1;i<=n;i++)cout<<dist3[i]<<' ';cout<<endl;

	set<pll> st;
	for(int i = 1;i<=n;i++){
		for(auto nxt:paths[i]){
			if(dist3[nxt.fs]+nxt.sc+dist[i] == dist[e]){
				st.insert(make_pair(i,nxt.fs));
				st.insert(make_pair(nxt.fs,i));
			}
		}
	}


	dist2[u] = 0;
	pq.push(make_pair(0LL,u));
	while(!pq.empty()){
		auto now = pq.top().sc;
		pq.pop();
		for(auto nxt:paths[now]){
			ll c = nxt.sc;
			if(st.find(make_pair(now,nxt.fs))!= st.end())c = 0;
			if(dist2[nxt.fs]>dist2[now]+c){
				dist2[nxt.fs] = dist2[now]+c;
				pq.push(make_pair(dist2[nxt.fs],nxt.fs));
			}
		}
	}
	//for(auto &i:st)cout<<i.fs<<' '<<i.sc<<',';cout<<endl;
	//for(int i = 1;i<=n;i++)cout<<dist2[i]<<',';cout<<endl;
	cout<<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: 0 / 24
• Subtask 4: 0 / 45