Submission #659043

#	Time	Username	Problem	Language	Result	Execution time	Memory
659043		rsjw	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	354 ms	33376 KiB

commuter_pass

#include <bits/stdc++.h>
#define W while
#define int long long
using namespace std;
#define mp make_pair
const int N = 200005;
namespace SSSP {
	struct edge {
		int to,w;
		edge *nex;
	}*head[N];
	void add(int u,int v,int w) {
		edge *cur=new edge;
		cur->to=v;
		cur->w=w;
		cur->nex=head[u];
		head[u]=cur;
	}
	int vis[N];
	priority_queue<pair<int,int>> q;
	void dij(int s,int d[],size_t size) {
		memset(vis,0,sizeof(vis));
		memset(d,0x2f,size);
		d[s]=0;
		q.push(mp(-d[s],s));

		W(!q.empty()) {
			int u=q.top().second;
			q.pop();
			if(vis[u]) continue ;
			vis[u]=1;
			for(edge *cur=head[u]; cur; cur=cur->nex) {
				if(d[cur->to]>d[u]+cur->w) {
					d[cur->to]=d[u]+cur->w;
					q.push(mp(-d[cur->to],cur->to));
				}
			}
		}
	}
} using namespace SSSP;
void chmin(int &x,int y) {
	x=min(x,y);
}
int du[N],dv[N],dt[N],ans;
namespace SSSP_EX {
	int d[N],fu[N],fv[N];
	priority_queue<pair<int,int>> q;
	void dp(int s) {
		memset(vis,0,sizeof(vis));
		memset(d,0x2f,sizeof(d));
		memset(fu,0x2f,sizeof(fu));
		memset(fv,0x2f,sizeof(fv));
		d[s]=0,fu[s]=du[s],ans=fu[s]+dv[s];
		q.push(mp(-d[s],s));
		fv[s]=dv[s];
		W(!q.empty()) {
			int u=q.top().second;
			q.pop();
			if(vis[u]) continue ;
			vis[u]=1;
			for(edge *cur=head[u]; cur; cur=cur->nex) {
				if(d[cur->to]>d[u]+cur->w) {
					fu[cur->to]=fv[cur->to]=0x2f2f2f2f2f2f2f2f;
					d[cur->to]=d[u]+cur->w;
					q.push(mp(-d[cur->to],cur->to));
				}
				if(d[cur->to]==d[u]+cur->w) {
					chmin(fu[cur->to],du[cur->to]);
					chmin(fu[cur->to],fu[u]);
					chmin(fv[cur->to],dv[cur->to]);
					chmin(fv[cur->to],fv[u]);
				}
			}
		}
	}
} using namespace SSSP_EX;
signed main() {
	//7338696
	ios::sync_with_stdio(0),cin.tie(0);
	int n,m,s,t,u,v,i;
	int x,y,z;
	cin>>n>>m>>s>>t>>u>>v;
	for(i=1; i<=m; i++) {
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	dij(u,du,sizeof du);
	dij(t,dt,sizeof dt);
	dij(v,dv,sizeof dv);
	dp(s);
	for(i=1; i<=n; i++) if(dt[s]==dt[i]+d[i]) chmin(ans,fu[i]+dv[i]);
	for(i=1; i<=n; i++) {
		if(dt[s]==dt[i]+d[i])
			chmin(ans,fv[i]+du[i]);
	}
	chmin(ans,du[v]);
	cout<<ans<<endl;
	return 0;
}

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