Submission #1110992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110992		haianhnguyen08102007	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	274 ms	69036 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+10;
ll n,m,s,t,u,v,x[N],y[N],z[N],d1[N],d2[N],d3[N],d4[N],ans;
struct graph
{
	ll cnt,dis[N],head[N],in[N],mind[N],v[N],f[N];
	struct Edge
	{
		ll nx,to,cost;
	}edg[N];
	struct node
	{
		ll id,ans;
		bool operator < (const node &x)const
		{
			return x.ans<ans;
		}
	};
	void add(int a,int b,int c)
	{
		edg[++cnt].to=b;
		edg[cnt].cost=c;
		edg[cnt].nx=head[a];
		in[b]++;
		head[a]=cnt;
	}
	priority_queue<node> q;
	void dj(int s,ll dis[])
	{
		for(int i=1;i<=n;i++)dis[i]=1ll*1e18;
		memset(v,0,sizeof(v));
		dis[s]=0;
		q.push((node){s,0});
		while(!q.empty())
		{
			node temp=q.top();
			q.pop();
			ll u=temp.id;
			if(v[u])continue;
			v[u]=1;
			for(int j=head[u];j;j=edg[j].nx)
			{
				int to=edg[j].to;
				if(dis[to]>dis[u]+edg[j].cost)
				{
					dis[to]=dis[u]+edg[j].cost;
					if(!v[to])q.push((node){to,dis[to]});
				}
			}
		}
	}
	void solve()
	{
		queue<int> q;
		for(int i=1;i<=n;i++)
		{
			mind[i]=d3[i];
			if(!in[i])q.push(i);
		}
		while(!q.empty())
		{
			int x=q.front();q.pop();
			if(f[x])continue;
			f[x]=1;
			ans=min(ans,mind[x]+d4[x]);
			for(int j=head[x];j;j=edg[j].nx)
			{
				int v=edg[j].to;
				in[v]--;mind[v]=min(mind[v],mind[x]);
				if(!in[v])q.push(v);
			}
		}
	}
}g1,g2,g3;
int main()
{
	ios::sync_with_stdio(0);

	cin>>n>>m>>s>>t>>u>>v;
	for(int i=1;i<=m;i++)
	{
		cin>>x[i]>>y[i]>>z[i];
		g1.add(x[i],y[i],z[i]);
		g1.add(y[i],x[i],z[i]);
	}
	g1.dj(s,d1);g1.dj(t,d2);g1.dj(u,d3);g1.dj(v,d4);
	ans=d3[v];
	for(int i=1;i<=m;i++)
	{
		if(d1[x[i]]+z[i]+d2[y[i]]==d1[t])g2.add(x[i],y[i],0),g3.add(y[i],x[i],0);
		else if(d1[y[i]]+z[i]+d2[x[i]]==d1[t])g2.add(y[i],x[i],0),g3.add(x[i],y[i],0);
	}
	g2.solve();g3.solve();
	cout<<ans<<'\n';
	return 0;
}

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