Submission #486213

#	Time	Username	Problem	Language	Result	Execution time	Memory
486213		iag99	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	288 ms	19828 KiB

commuter_pass

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <bitset>
#include <set>
#include <fstream>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
const ll INF=LLONG_MAX/2;
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//cout.tie(0);
	//freopen("shortcut.in", "r", stdin);
	//freopen("shortcut.out", "w", stdout);
	ll n,m;
	cin>>n>>m;
	ll s,t;
	cin>>s>>t;
	ll u,v;
	cin>>u>>v;
	vector<pair<ll,ll> > adj[n+1];
	for(int i=0; i<m; i++)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		adj[a].push_back(make_pair(c, b));
		adj[b].push_back(make_pair(c,a));
	}
	vector<ll> du(n+1,INF),dv(n+1, INF),ds(n+1, INF),dt(n+1, INF);
	priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > pq;
	du[u]=0;
	pq.push(make_pair(0,u));
	while(!pq.empty())
	{
		ll cur=pq.top().second;
		ll c=pq.top().first;
		pq.pop();
		if(du[cur]!=c) continue;
		for(auto to : adj[cur])
		{
			ll ver=to.second;
			ll w=to.first;
			if(du[cur]+w<du[ver])
			{
				du[ver]=du[cur]+w;
				pq.push(make_pair(du[ver],ver));
			}
		}
	}
	dv[v]=0;
	pq.push(make_pair(0,v));
	while(!pq.empty())
	{
		ll cur=pq.top().second;
		ll c=pq.top().first;
		pq.pop();
		if(dv[cur]!=c) continue;
		for(auto to : adj[cur])
		{
			ll ver=to.second;
			ll w=to.first;
			if(dv[cur]+w<dv[ver])
			{
				dv[ver]=dv[cur]+w;
				pq.push(make_pair(dv[ver],ver));
			}
		}
	}
	vector<ll> dpU(n+1,INF);
	vector<ll> dpV(n+1,INF);
	ds[s]=0;
	pq.push(make_pair(0,s));
	while(!pq.empty())
	{
		ll cur=pq.top().second;
		ll c=pq.top().first;
		pq.pop();
		if(ds[cur]!=c)
		{
			continue;
		}
		for(auto to: adj[cur])
		{
			ll ver=to.second;
			ll w=to.first;
			if(ds[cur]+w<ds[ver])
			{
				ds[ver]=ds[cur]+w;
				pq.push(make_pair(ds[ver],ver));
				dpU[ver]=min(du[ver], dpU[cur]);
				dpV[ver]=min(dv[ver], dpV[cur]);
			}
			
		}
	}
	ll ans=du[v];
	ans=min(ans, dpU[t]+dpV[t]);
	
	dpU.resize(n+1,INF);
	dpV.resize(n+1,INF);
	dt[t]=0;
	pq.push(make_pair(0,t));
	while(!pq.empty())
	{
		ll cur=pq.top().second;
		ll c=pq.top().first;
		pq.pop();
		if(dt[cur]!=c)
		{
			continue;
		}
		for(auto to: adj[cur])
		{
			ll ver=to.second;
			ll w=to.first;
			if(dt[cur]+w<dt[ver])
			{
				dt[ver]=dt[cur]+w;
				pq.push(make_pair(dt[ver],ver));
				dpU[ver]=min(du[ver], dpU[cur]);
				dpV[ver]=min(dv[ver], dpV[cur]);
			}
			
		}
	}
	ll ans2=dv[u];
	ans2=min(ans2, dpU[s]+dpV[s]);
	ll ansfinal=min(ans, ans2);
	cout<<ansfinal<<endl;
	return 0;
 
}

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