Submission #310902

#	Time	Username	Problem	Language	Result	Execution time	Memory
310902		T0p_	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2082 ms	21488 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;
	bool operator < (const DJK & o) const
	{
		return weight > o.weight;		
	}	
};

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

bool visit[100100];
long long dis_s[100100], dis_u[100100], dis_v[100100];
vector<GRAPH> g[100100];
priority_queue<DJK> djk;
stack<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 u, v;
		long long w;
		scanf(" %d %d %lld",&u,&v,&w);
		g[u].pb({v, w});
		g[v].pb({u, w});
	}

	for(int i=1 ; i<=n ; i++)
		dis_s[i] = dis_u[i] = dis_v[i] = 1e15;
	dis_s[s] = dis_u[u] = dis_v[v] = 0;

	for(int i=1 ; i<=n ; i++)
		visit[i] = false;
	djk.push({s, 0});
	while(!djk.empty())
	{
		int nown = djk.top().node;
		long long noww = djk.top().weight;
		djk.pop();
		if(visit[nown]) continue ;
		visit[nown] = true;
		for(auto x : g[nown])
			if(dis_s[x.node] > noww + x.weight)
			{
				dis_s[x.node] = noww + x.weight;
				djk.push({x.node, dis_s[x.node]});
			}
	}

	for(int i=1 ; i<=n ; i++)
		visit[i] = false;
	djk.push({u, 0});
	while(!djk.empty())
	{
		int nown = djk.top().node;
		long long noww = djk.top().weight;
		djk.pop();
		if(visit[nown]) continue ;
		visit[nown] = true;
		for(auto x : g[nown])
			if(dis_u[x.node] > noww + x.weight)
			{
				dis_u[x.node] = noww + x.weight;
				djk.push({x.node, dis_u[x.node]});
			}
	}

	for(int i=1 ; i<=n ; i++)
		visit[i] = false;
	djk.push({v, 0});
	while(!djk.empty())
	{
		int nown = djk.top().node;
		long long noww = djk.top().weight;
		djk.pop();
		if(visit[nown]) continue ;
		visit[nown] = true;
		for(auto x : g[nown])
			if(dis_v[x.node] > noww + x.weight)
			{
				dis_v[x.node] = noww + x.weight;
				djk.push({x.node, dis_v[x.node]});
			}
	}

	long long ans = 1e15;

	// min v
	bt.push({t, 1000000000000000});
	while(!bt.empty())
	{
		int nown = bt.top().node;
		long long noww = bt.top().weight;
		bt.pop();
		ans = min(ans, dis_u[nown] + noww);
		for(auto x : g[nown])
			if(dis_s[x.node] + x.weight == dis_s[nown])
				bt.push({x.node, min(dis_v[x.node], noww)});
	}

	// min u
	bt.push({t, 1000000000000000});
	while(!bt.empty())
	{
		int nown = bt.top().node;
		long long noww = bt.top().weight;
		bt.pop();
		ans = min(ans, dis_v[nown] + noww);
		for(auto x : g[nown])
			if(dis_s[x.node] + x.weight == dis_s[nown])
				bt.push({x.node, min(dis_u[x.node], noww)});
	}

	printf("%lld\n",min(ans, dis_u[v]));
	return 0;
}

Compilation message (stderr)

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

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