Submission #963844

#	Time	Username	Problem	Language	Result	Execution time	Memory
963844		starchan	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	250 ms	31308 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

vector<in> adj[MX];

void dijsktra(int n, int src, vector<int> &dist)
{
	priority_queue<in> pq;
	dist.assign(n+1, INF);
	pq.push({dist[src] = 0, src});
	while(pq.size())
	{
		auto [wp, U] = pq.top(); wp = -wp; pq.pop();
		if(dist[U] < wp)
			continue;
		for(auto [v, w]: adj[U])
		{
			if(dist[v] > (dist[U]+w))
			{
				dist[v] = dist[U]+w;
				pq.push({-dist[v], v});
			}
		}
	}
	return;
}

signed main()
{
	fast();
	int n, m;
	cin >> n >> m;
	int S, T, U, V;
	cin >> S >> T >> U >> V;
	while(m--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}
	vector<int> d1, d2;
	dijsktra(n, U, d1); dijsktra(n, V, d2);
	vector<int> dist; dist.assign(n+1, INF);

	/*for(int i = 1; i <= n; i++)
		cout << d1[i] << " ";
	cout << endl;
	for(int i = 1; i <= n; i++)
		cout << d2[i] << " ";
	cout << endl;*/

	int cnt[4][n+1];

	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j < 4; j++)
			cnt[j][i] = INF;
	}

	cnt[1][S] = d1[S]; cnt[2][S] = d2[S]; cnt[3][S] = d1[S]+d2[S];

	dist.assign(n+1, INF);
	priority_queue<in> pq;
	pq.push({dist[S] = 0, S});
	while(pq.size())
	{
		auto [wp, u] = pq.top(); wp = -wp; pq.pop();
		if(dist[u] < wp)
			continue;
		for(auto [v, w]: adj[u])
		{
			if(dist[v] > (dist[u]+w))
			{
				dist[v] = dist[u]+w;
				pq.push({-dist[v], v});
				cnt[1][v] = min(cnt[1][u], d1[v]);
				cnt[2][v] = min(cnt[2][u], d2[v]);
				cnt[3][v] = min(cnt[3][u], min(d1[v] + cnt[2][u], d2[v] + cnt[1][u]));
				cnt[3][v] = min(cnt[3][v], d1[v]+d2[v]);
			}
			else if(dist[v] == (dist[u]+w))
			{
				cnt[1][v] = min(cnt[1][v], cnt[1][u]);
				cnt[2][v] = min(cnt[2][v], cnt[2][u]);
				cnt[3][v] = min(cnt[3][v], min(d1[v] + cnt[2][u], d2[v] + cnt[1][u]));
				cnt[3][v] = min(cnt[3][v], cnt[3][u]);
			}
		}
	}
	int ans = min(d1[V], cnt[3][T]);
	cout << ans << "\n";
	return 0;
}	

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