Submission #480490

#	Time	Username	Problem	Language	Result	Execution time	Memory
480490		ymm	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	862 ms	68608 KiB

commuter_pass

///
///   ♪ Pizza mozzarella rella rella rella... ♪
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 100'010;
const ll inf = 1e15;
int n, m;
int s, t;
int u, v;

vector<ll> dij(vector<pll>* A, int s, int n, vector<int>* par = NULL)
{
	vector<ll> dis(n);
	set<pll> pq;
	Loop(i,0,n) dis[i] = (i==s?0:inf);
	pq.emplace(0,s);
	while(pq.size())
	{
		auto v = pq.begin()->second;
		pq.erase(pq.begin());
		for(auto [u, w] : A[v])
		{
			if(dis[v] + w < dis[u])
			{
				if(par) par[u].clear();
				pq.erase ({dis[u], u});
				dis[u] = dis[v] + w;
				pq.insert({dis[u], u});
			}
			if(dis[v] + w == dis[u] && par)
				par[u].push_back(v);
		}
	}
	return dis;
}

vector<pll> A[4*N];
vector<int> par[N];

bool vis[N];
void jotaro(int v)
{
	vis[v] = 1;
	for(auto p : par[v]){
		A[n+p].emplace_back(n+v,0);
		A[2*n+v].emplace_back(2*n+p,0);
		if(!vis[p])
			jotaro(p);
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> s >> t >> u >> v;
	--s; --t; --u; --v;
	Loop(_,0,m)
	{
		int v, u, w;
		cin >> v >> u >> w;
		--v; --u;
		A[v].emplace_back(u,w);
		A[u].emplace_back(v,w);
		A[3*n+v].emplace_back(3*n+u,w);
		A[3*n+u].emplace_back(3*n+v,w);
	}
	dij(A, s, n, par);
	jotaro(t);
	Loop(i,0,n)
	{
		A[0*n+i].emplace_back(1*n+i, 0);
		A[0*n+i].emplace_back(2*n+i, 0);
		A[1*n+i].emplace_back(3*n+i, 0);
		A[2*n+i].emplace_back(3*n+i, 0);
	}
	cout << dij(A, v, 4*n)[3*n+u] << '\n';
}

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