Submission #899071

#	Time	Username	Problem	Language	Result	Execution time	Memory
899071		pan	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	3367 ms	211000 KiB

RelayMarathon

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
ll n, m, k;
ll ans = LLONG_MAX;
vector<pi> adj[100005];
bool special[100005], skip[100005];
vector<ll> dist;
ll par[100005];

ll b1, b2, distan;

void findclosestpair()
{
	b1= -1, b2=-1;
	distan = LLONG_MAX;
	priority_queue<pi, vector<pi>, greater<pi> > pq;
	dist.assign(n+1, LLONG_MAX);
	for (ll i=1; i<=n; ++i)
	{
		if (!special[i] || skip[i]) continue;
		dist[i] = 0;
		pq.push(mp(dist[i], i));
		par[i] = i;
		
	}
	while (!pq.empty())
	{
		pi temp = pq.top();
		ll from = temp.second;
		pq.pop();
		//if (dist[from]< temp.f) continue;
		for (pi u: adj[from])
		{
			if (!skip[u.f] && dist[u.f]>dist[from]+u.s)
			{
				dist[u.f] = dist[from] + u.s;
				par[u.f] = par[from];
				pq.push(mp(dist[u.f], u.f));
			}
		}
	}
	for (ll i=1; i<=n; ++i)
	{
		if (skip[par[i]]) continue;
		for(pi u: adj[i])
		{
			if (par[u.f]==par[i] || skip[par[u.f]]) continue;
			if (dist[i] + u.s + dist[u.f] < distan)
			{
				distan = dist[i] + u.s + dist[u.f];
				b1 = par[i], b2 = par[u.f];
			}
		}
	}
	
}

vector<ll> dijkstra(ll src)
{

	priority_queue<pi, vector<pi>, greater<pi> > pq;
	vector<ll> dist(n+1, LLONG_MAX);
	dist[src] = 0;
	pq.push(mp(0, src));
	while (!pq.empty())
	{
		ll from = pq.top().second;
		pq.pop();
		for (pi u: adj[from])
		{
			if (dist[u.f]>dist[from]+u.s)
			{
				dist[u.f] = dist[from] + u.s;
				pq.push(mp(dist[u.f], u.f));
			}
		}
	}
	return dist;
}
int main()
{
	cin >> n >> m >> k;
	for (ll i=0; i<m; ++i)
	{
		ll a,b,c;
		cin >> a >> b >> c;
		adj[a].pb(mp(b,c));
		adj[b].pb(mp(a,c));
	}
	for (ll i=1; i<=k; ++i) 
	{
		ll a;
		cin >> a;
		special[a] = 1;
	}
	//cout << "done" << endl;
	// find x1, x2 (closest pair)
	findclosestpair();
	// case 1: join (x1, x2) -> find another paur
	ll add = distan;
	ll a = b1, b = b2;
	//cout << a << b << endl;
	skip[a] = 1, skip[b] = 1;
	findclosestpair();
	ans = add+ distan;
	//cout << "done" << endl;
	//cout << ans << endl;
	// case 2: seperate x1 from x2 -> pair both up
	vector<ll> fromb1 = dijkstra(a), fromb2 = dijkstra(b);
	vector<pi> choose1, choose2;
	for (ll i=1; i<=n; ++i) 
	{
		if (i==a || i==b || !special[i]) continue;
		choose1.pb(mp(fromb1[i], i));
		choose2.pb(mp(fromb2[i], i));
	}
	//cout << "done" << endl;
	sort(choose1.begin(), choose1.end());
	sort(choose2.begin(), choose2.end());
	if (choose1[0].s == choose2[0].s)
	{
		//cout << "one" << endl;
		//cout << choose1[0].s << endl;
		if (choose1[1].f!=LLONG_MAX && choose2[0].f!=LLONG_MAX) ans = min(ans, choose1[1].f + choose2[0].f);
		if (choose2[1].f!=LLONG_MAX && choose1[0].f!=LLONG_MAX) ans = min(ans, choose2[1].f + choose1[0].f);
	}
	else
	{
		if (choose1[0].f!=LLONG_MAX && choose2[0].f!=LLONG_MAX) ans = min(ans, choose1[0].f + choose2[0].f);
		//cout << choose1[0].f  << ' ' << choose2[0].f << endl;
	}
	cout << ans << endl;
	
	
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 58 / 58