Submission #96166

#	Time	Username	Problem	Language	Result	Execution time	Memory
96166		gumball	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	764 ms	38960 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,S,T,U,V,i,dis[101010][6],ta,tb,tc,b[101010][6],j,d[101010][2],has;
vector<ll> v[101010],w[101010],x[101010];
void djik(ll aa,ll bb)
{
	priority_queue<pair<ll,pair<ll,ll> > > pq;
	ll ii;
	for(ii=1;ii<=n;ii++)dis[ii][bb]=1e18;
	dis[aa][bb]=0;
	pq.push(mp(0,mp(aa,-1)));
	while(!pq.empty())
	{
		ll jar=-pq.top().fi;
		ll u=pq.top().se.fi;
		ll par=pq.top().se.se;
		pq.pop();
		if(b[u][bb])continue;
		b[u][bb]=1;
		for(ii=0;ii<v[u].size();ii++)
		{
			ll nx=v[u][ii];
			if(dis[nx][bb]>=(jar+w[u][ii]))
			{
				dis[nx][bb]=jar+w[u][ii];
				pq.push(mp(-jar-w[u][ii],mp(nx,u)));
			}
		}
	}
}
ll depe(ll aa,ll bb)
{
	if(d[aa][bb]==-1)
	{
		if(bb==0)
			d[aa][bb]=dis[aa][2];
		else
			d[aa][bb]=dis[aa][3];
		ll ii;
		for(ii=0;ii<x[aa].size();ii++)
			d[aa][bb]=min(d[aa][bb],depe(x[aa][ii],bb));
	}
	return d[aa][bb];
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m;
	cin>>S>>T;
	cin>>U>>V;
	for(i=1;i<=m;i++)
	{
		cin>>ta>>tb>>tc;
		v[ta].pb(tb);
		v[tb].pb(ta);
		w[ta].pb(tc);
		w[tb].pb(tc);
	}
	djik(S,0);
	djik(T,1);
	djik(U,2);
	djik(V,3);
	for(i=1;i<=n;i++)
	{
		for(j=0;j<v[i].size();j++)
		{
			if((dis[i][0]+w[i][j]+dis[v[i][j]][1])==dis[T][0])
			{
			//	cout<<i<<" "<<v[i][j]<<"\n";
				x[v[i][j]].pb(i);
			}
		}
	}
	has=1e18;
	memset(d,-1,sizeof(d));
	for(i=1;i<=n;i++)
	{
		//cout<<i<<" "<<depe(i,0)<<" "<<depe(i,1)<<"\n";
		has=min(has,depe(i,0)+dis[i][3]);
		has=min(has,depe(i,1)+dis[i][2]);
	}
	cout<<has<<"\n";
	//for(i=1;i<=n;i++)cout<<i<<" S="<<dis[i][2]<<" T="<<dis[i][3]<<"\n";
}	

Compilation message (stderr)

commuter_pass.cpp: In function 'void djik(long long int, long long int)':
commuter_pass.cpp:25:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[u].size();ii++)
            ~~^~~~~~~~~~~~
commuter_pass.cpp:21:6: warning: unused variable 'par' [-Wunused-variable]
   ll par=pq.top().se.se;
      ^~~
commuter_pass.cpp: In function 'long long int depe(long long int, long long int)':
commuter_pass.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<x[aa].size();ii++)
            ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<v[i].size();j++)
           ~^~~~~~~~~~~~

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