Submission #310906

#	Time	Username	Problem	Language	Result	Execution time	Memory
310906		T0p_	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	493 ms	26580 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

struct GRAPH
{
	int node;
	long long weight;
};

struct DJK
{
	int node;
	long long weight;
	int state;
	bool operator < (const DJK & o) const
	{
		return weight > o.weight;		
	}	
};

struct BT
{
	int node;
	long long weight;
	bool operator < (const BT & o) const
	{
		return weight > o.weight;	
	}
};

bool visit[3][100100];
long long dis[3][100100], disbt[100100];
vector<GRAPH> g[100100];
priority_queue<DJK> djk;
priority_queue<BT> bt;

int main()
{
	int n, m, s, t, u, v;
	scanf(" %d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
	while(m--)
	{
		int a, b;
		long long w;
		scanf(" %d %d %lld",&a,&b,&w);
		g[a].pb({b, w});
		g[b].pb({a, w});
	}

	for(int i=1 ; i<=n ; i++)
		dis[0][i] = dis[1][i] = dis[2][i] = 1e15;
	dis[0][s] = dis[1][u] = dis[2][v] = 0;

	djk.push({s, 0, 0});
	djk.push({u, 0, 1});
	djk.push({v, 0, 2});
	while(!djk.empty())
	{
		int nown = djk.top().node;
		long long noww = djk.top().weight;
		int nows = djk.top().state;
		djk.pop();
		if(visit[nows][nown]) continue ;
		visit[nows][nown] = true;
		for(auto x : g[nown])
			if(dis[nows][x.node] > noww + x.weight)
			{
				dis[nows][x.node] = noww + x.weight;
				djk.push({x.node, dis[nows][x.node], nows});
			}
	}

	long long ans = dis[1][v];

	// u
	for(int i=1 ; i<=n ; i++)
		disbt[i] = 1e15;
	bt.push({t, 1000000000000000});
	while(!bt.empty())
	{
		int nown = bt.top().node;
		long long noww = bt.top().weight;
		bt.pop();
		ans = min(ans, dis[2][nown] + noww);
		for(auto x : g[nown])
		{
			long long ww = min(dis[1][nown], noww);
			if(dis[0][x.node] + x.weight == dis[0][nown] && disbt[x.node] > ww)
			{
				disbt[x.node] = ww;
				bt.push({x.node, min(dis[1][nown], noww)});
			}
		}
	}

	// v
	for(int i=1 ; i<=n ; i++)
		disbt[i] = 1e15;
	bt.push({t, 1000000000000000});
	while(!bt.empty())
	{
		int nown = bt.top().node;
		long long noww = bt.top().weight;
		bt.pop();
		ans = min(ans, dis[1][nown] + noww);
		for(auto x : g[nown])
		{
			long long ww = min(dis[2][nown], noww);
			if(dis[0][x.node] + x.weight == dis[0][nown] && disbt[x.node] > ww)
			{
				disbt[x.node] = ww;
				bt.push({x.node, min(dis[2][nown], noww)});
			}
		}
	}

	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf(" %d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf(" %d %d %lld",&a,&b,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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