Submission #293123

#	Time	Username	Problem	Language	Result	Execution time	Memory
293123		Pyqe	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	597 ms	44976 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,m,st[2],fn[2],wg[200069],nr[2][100069],inf=1e18;
pair<long long,long long> ed[200069];
vector<pair<long long,long long>> al[100069];
priority_queue<pair<long long,pair<bool,long long>>> pq;
vector<long long> cd[2][100069];
bitset<100069> vtd[2];

void dfs(long long xx,long long x,long long w)
{
	long long i,sz=cd[xx][x].size(),l;
	
	vtd[xx][x]=1;
	if(w<nr[1][x])
	{
		pq.push({-w,{1,x}});
		nr[1][x]=w;
	}
	for(i=0;i<sz;i++)
	{
		l=cd[xx][x][i];
		if(!vtd[xx][l])
		{
			dfs(xx,l,w);
		}
	}
}

int main()
{
	long long i,ii,k,l,w,sz,ww,e;
	
	scanf("%lld%lld",&n,&m);
	for(ii=0;ii<2;ii++)
	{
		scanf("%lld%lld",st+ii,fn+ii);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&k,&l,&w);
		ed[i]={k,l};
		wg[i]=w;
		al[k].push_back({l,w});
		al[l].push_back({k,w});
	}
	for(ii=0;ii<2;ii++)
	{
		for(i=1;i<=n;i++)
		{
			nr[ii][i]=inf;
		}
		pq.push({0,{ii,st[0]}});
		nr[ii][st[0]]=0;
		swap(st[0],fn[0]);
	}
	for(;!pq.empty();)
	{
		e=pq.top().sc.fr;
		k=pq.top().sc.sc;
		w=-pq.top().fr;
		pq.pop();
		if(w>nr[e][k])
		{
			continue;
		}
		sz=al[k].size();
		for(i=0;i<sz;i++)
		{
			l=al[k][i].fr;
			ww=al[k][i].sc;
			if(w+ww<nr[e][l])
			{
				pq.push({-w-ww,{e,l}});
				nr[e][l]=w+ww;
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		k=ed[i].fr;
		l=ed[i].sc;
		if(nr[0][k]>nr[0][l])
		{
			swap(k,l);
		}
		if(nr[0][k]+wg[i]+nr[1][l]==nr[0][fn[0]])
		{
			cd[0][k].push_back(l);
			cd[1][l].push_back(k);
		}
	}
	for(ii=0;ii<2;ii++)
	{
		for(i=1;i<=n;i++)
		{
			nr[ii][i]=inf;
		}
	}
	pq.push({0,{0,st[1]}});
	nr[0][st[1]]=0;
	for(;!pq.empty();)
	{
		e=pq.top().sc.fr;
		k=pq.top().sc.sc;
		w=-pq.top().fr;
		pq.pop();
		if(w>nr[e][k])
		{
			continue;
		}
		if(!e)
		{
			for(ii=0;ii<2;ii++)
			{
				if(!vtd[ii][k])
				{
					dfs(ii,k,w);
				}
			}
		}
		sz=al[k].size();
		for(i=0;i<sz;i++)
		{
			l=al[k][i].fr;
			ww=al[k][i].sc;
			if(w+ww<nr[e][l])
			{
				pq.push({-w-ww,{e,l}});
				nr[e][l]=w+ww;
			}
		}
	}
	printf("%lld\n",nr[1][fn[1]]);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%lld%lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%lld%lld",st+ii,fn+ii);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%lld%lld%lld",&k,&l,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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