Submission #116094

#	Time	Username	Problem	Language	Result	Execution time	Memory
116094		faustaadp	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	682 ms	31356 KiB

commuter_pass

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

Compilation message (stderr)

commuter_pass.cpp: In function 'll depe(ll, ll)':
commuter_pass.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<vi[aa].size();ii++)
            ~~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void buat(ll, ll)':
commuter_pass.cpp:40:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[u].size();ii++)
            ~~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:68: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