Submission #879209

#	Time	Username	Problem	Language	Result	Execution time	Memory
879209		mahmoudbadawy	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	321 ms	19284 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,m;
vector< pair<int,int> > adj[N];

long long dis[4][N];
int sp[4];

void calc(int ind)
{
	for(int i=1;i<=n;i++) dis[ind][i]=(1LL<<60);
	int x=sp[ind];
	dis[ind][x]=0;
	set<pair<long long,int> > ss;
	ss.insert({0,x});
	while(ss.size())
	{
		int u=(*ss.begin()).second;
		ss.erase(ss.begin());
		for(auto i:adj[u])
		{
			int v=i.first, c=i.second;
			if(dis[ind][u]+c < dis[ind][v])
			{
				if(dis[ind][v]!=(1LL<<60)) ss.erase({dis[ind][v],v});
				dis[ind][v]=dis[ind][u]+c;
				ss.insert({dis[ind][v],v});
			}
		}
	}
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<4;i++) scanf("%d",&sp[i]);
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		adj[x].push_back({y,z});
		adj[y].push_back({x,z});
	}
	for(int i=0;i<4;i++) calc(i);
	long long a=(1LL<<60), b=(1LL<<60);
	for(int i=1;i<=n;i++)
	{
		if(dis[0][i]+dis[1][i]==dis[0][sp[1]]) // (S to i) + (i to T) = (S to T)
		{
			a=min(a, dis[2][i]); // U to i
			b=min(b, dis[3][i]); // i to V
		}
	}
	//cout << a << " " << b << endl;
	printf("%lld\n", min(a+b, dis[2][sp[3]]));
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:40:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  for(int i=0;i<4;i++) scanf("%d",&sp[i]);
      |                       ~~~~~^~~~~~~~~~~~~
commuter_pass.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d %d %d",&x,&y,&z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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