Submission #310903

#	Time	Username	Problem	Language	Result	Execution time	Memory
310903		T0p_	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2100 ms	25612 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 wmu, wmv;
};

bool visit[3][100100];
long long dis[3][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[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];

	bt.push({t, 1000000000000000, 1000000000000000});
	while(!bt.empty())
	{
		int nown = bt.top().node;
		long long nowu = bt.top().wmu;
		long long nowv = bt.top().wmv;
		bt.pop();
		ans = min(ans, min(dis[1][nown] + nowv, dis[2][nown] + nowu));
		for(auto x : g[nown])
			if(dis[0][x.node] + x.weight == dis[0][nown])
				bt.push({x.node, min(dis[1][nown], nowu), min(dis[2][nown], nowv)});
	}

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

Compilation message (stderr)

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

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