Submission #712245

#	Time	Username	Problem	Language	Result	Execution time	Memory
712245		dozer	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	572 ms	30688 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define int long long

const int modulo = 1e9 + 7, INF = 2e18 + 7;

int d[2][N];
pii dist[2][2][N];
vector<pii> adj[N];

pii neg(pii tmp)
{
	return {-tmp.st, -tmp.nd};
}

int32_t main()
{
	fastio();

	int n, m, s, t , u, v;
	cin>>n>>m;
	cin>>s>>t>>u>>v;

	for (int i = 0; i < 2; i++) 
		for (int j = 0; j < 2; j++)
			for (int k = 1; k <= n; k++) dist[i][j][k] = {INF, INF}, d[i][k] = INF;

	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin>>a>>b>>c;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	
	auto dijkstra1 = [&](int root){
		int curr = u;
		if (root) curr = v;
		priority_queue<pii> q;
		d[root][curr] = 0;
		q.push({0, curr});
		while(!q.empty())
		{
			int top = q.top().nd;
			q.pop();
			for (auto i : adj[top])
			{
				int to = i.st, w = i.nd;
				if (d[root][to] > d[root][top] + w)
				{
					d[root][to] = d[root][top] + w;
					q.push({-d[root][to], to});
				}
			}
		}
	};


	dijkstra1(0);
	dijkstra1(1);

	auto dijkstra2 = [&](int r1, int r2){
		int curr = s;
		if (r1) curr = t;
		dist[r1][r2][curr] = {0, d[r2][curr]};
		priority_queue<pair<pii ,int>> q;
		q.push({neg(dist[r1][r2][curr]), curr});
		while(!q.empty())
		{
			int top = q.top().nd;
			pii tmp = neg(q.top().st);
			q.pop();
			for (auto i : adj[top])
			{
				int to = i.st, w = i.nd;
				pii tmptmp = tmp;
				tmptmp.st += w;
				tmptmp.nd = min(tmptmp.nd, d[r2][to]);
				if (dist[r1][r2][to] > tmptmp)
				{
					dist[r1][r2][to] = tmptmp;
					q.push({neg(dist[r1][r2][to]), to});
				}
			}
		}
	};

	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) dijkstra2(i, j);
	int ans = d[0][v];
	for (int i = 1; i <= n; i++)
	{
		if (dist[0][0][i].st + dist[1][0][i].st == dist[0][0][t].st)
		{
			//cout<<i<<sp<<dist[0][0][i].nd<<sp<<dist[0][1][i].nd<<sp<<dist[1][0][i].nd<<sp<<dist[1][1][i].nd<<endl;
			ans = min(ans, dist[0][0][i].nd + dist[1][1][i].nd);
			ans = min(ans, dist[0][1][i].nd + dist[1][0][i].nd);
		}
	}

	cout<<ans<<endl;

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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