Submission #853959

#	Time	Username	Problem	Language	Result	Execution time	Memory
853959		parsadox2	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	425 ms	94696 KiB

commuter_pass

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

const int N = 1e6 + 2;
int n , m , s , t , ss , tt , dis[2][N] , slm[3][N];
vector <pair<int , int>> adj[N];
bool marked[N];

void dij(int star , int h[])
{
	memset(h , 63 , N);  memset(marked , false , sizeof marked);
	h[star] = 0;
	priority_queue <pair<int , int>> pq;
	pq.push({0 , star});
	while(!pq.empty())
	{
		auto now = pq.top();  pq.pop();
		int v = now.second , D = abs(now.first);
		if(marked[v])
			continue;
		marked[v] = true;
		for(auto u : adj[v])  if(h[u.first] > D + u.second)
		{
			h[u.first] = D + u.second;
			pq.push({-h[u.first] , u.first});
		}
	}
}

bool mrk[3][N];

void solve(int star)
{
	memset(slm , 63 , sizeof slm);
	memset(mrk , false , sizeof mrk);
	slm[0][star] = 0;
	priority_queue <pair<int , pair<int , int>>> pq;
	pq.push({0 , {0 , star}});
	while(!pq.empty())
	{
		auto now = pq.top();  pq.pop();
		int v = now.second.second , ty = now.second.first , D = abs(now.first);
		if(mrk[ty][v])
			continue;
		mrk[ty][v] = true;
		for(auto u : adj[v])
		{
			if(u.second == 0 && ty <= 1 && slm[1][u.first] > D)
			{
				slm[1][u.first] = D;
				pq.push({-D , {1 , u.first}});
			}
			if(u.second > 0 && ty == 0 && slm[0][u.first] > D + u.second)
			{
				slm[0][u.first] = D + u.second;
				pq.push({-slm[0][u.first] , {0 , u.first}});
			}
			if(u.second > 0 && ty >= 1 && slm[2][u.first] > D + u.second)
			{
				slm[2][u.first] = D + u.second;
				pq.push({-slm[2][u.first] , {2 , u.first}});
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n >> m >> s >> t >> ss >> tt;
	vector <pair<pair<int , int> , int>> edges;
	while(m--)
	{
		int a , b , w;
		cin >> a >> b >> w;
		adj[a].push_back({b , w});
		adj[b].push_back({a , w});
		edges.push_back({{a , b} , w});
	}
	dij(s , dis[0]);
	dij(t , dis[1]);
	for(auto e : edges)
	{
		int a = e.first.first , b = e.first.second , w = e.second;
		if(dis[0][a] + dis[1][b] + w == dis[0][t])
			adj[a].push_back({b , 0});
		if(dis[0][b] + dis[1][a] + w == dis[0][t])
			adj[b].push_back({a , 0});
	}
	solve(ss);
	int ans = min({slm[0][tt] , slm[1][tt] , slm[2][tt]});
	solve(tt);
	ans = min({ans , slm[0][ss] , slm[1][ss] , slm[2][ss]});
	cout << ans << '\n';
	return 0;
}

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