Submission #261259

#	Time	Username	Problem	Language	Result	Execution time	Memory
261259		Berted	Relay Marathon (NOI20_relaymarathon)	C++14	100 / 100	1686 ms	127816 KiB

RelayMarathon

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <bitset>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define ppp pair<pii, pii>
#define fst first
#define snd second
#define vi vector<int>
#define vpi vector<pii>
#define pub push_back
using namespace std;
vector<vpi> adj;
priority_queue<ppi, vector<ppi>, greater<ppi>> pq;
bitset<100001> special;

const int MX = 1000000000;

int n, m, k, visited[100001][2] = {};

//inline int getchar_unlocked() {return getchar();}
inline bool isNum(char c) {return '0' <= c && c <= '9';}
inline int fast_input()
{
	int c = 0, rs = 0;
	while (!isNum(c)) {c = getchar_unlocked();}
	while (isNum(c)) 
	{

		rs = 10 * rs + (c - '0');
		c = getchar_unlocked();
	}
	return rs;
}

inline ppp dijkstra(int s)
{
	int u, c;
	for (int i = 0; i < n; i++) {visited[i][0] = MX;}
	ppp tp = {{-1, -1}, {-1, -1}};
	pq.push({{0, s}, 0});
	while (!pq.empty())
	{
		u = pq.top().fst.snd, c = pq.top().fst.fst; pq.pop();
		if (c <= visited[u][0])
		{
			visited[u][0] = c;
			if (special[u]) 
			{
				if (tp.fst.fst == -1) {tp.fst = {u, c};}
				else if (tp.snd.fst == -1) 
				{
					tp.snd = {u, c}; 
					while (pq.size()) {pq.pop();}
					return tp;
				}
			}
			for (auto v : adj[u])
			{
				 if (c + v.snd < visited[v.fst][0]) 
				 {
				 	visited[v.fst][0] = c + v.snd;
				 	pq.push({{c + v.snd, v.fst}, 0});
				 }
			}
		}
	}
	return tp;
}

inline ppi findShortestPair()
{
	int u, c, p;
	for (int i = 0; i < n; i++) {visited[i][0] = MX; visited[i][1] = -1;}
	ppi rs = {{-1, -1}, MX};
	while (!pq.empty())
	{
		u = pq.top().fst.snd, c = pq.top().fst.fst, p = pq.top().snd; pq.pop(); 
		if (c <= visited[u][0])
		{
			visited[u][0] = c;
			visited[u][1] = p;
			for (auto v : adj[u])
			{
				if (c + v.snd < visited[v.fst][0])
				{
					if (visited[v.fst][0] + c + v.snd < rs.snd && visited[v.fst][1] != -1 && visited[v.fst][1] != p)
					{
						rs.fst.fst = visited[v.fst][1];
						rs.fst.snd = p;
						rs.snd = visited[v.fst][0] + c + v.snd;
					}
					visited[v.fst][0] = c + v.snd;
					visited[v.fst][1] = p;
					pq.push({{c + v.snd, v.fst}, p});
				}
				else if (visited[v.fst][0] + c + v.snd < rs.snd && visited[v.fst][1] != p)
				{
					rs.fst.fst = visited[v.fst][1];
					rs.fst.snd = p;
					rs.snd = visited[v.fst][0] + c + v.snd;
				}
			}
		}
	}
	return rs;
}

int main()
{
	n = fast_input();
	m = fast_input();
	k = fast_input();
	for (int i = 0; i < n; i++) {adj.pub(vpi());}
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		u = fast_input();
		v = fast_input();
		w = fast_input();
		adj[u - 1].pub({v - 1, w});
		adj[v - 1].pub({u - 1, w});
	}
	for (int i = 0; i < k; i++) 
	{
		int x;
		x = fast_input();
		special[x - 1] = 1;
		//mp[find(x - 1)].pub(x);
		pq.push({{0, x - 1}, x - 1});
	}
	int rs = 1e9;
	ppi rs1 = findShortestPair();
	special[rs1.fst.snd] = 0;
	special[rs1.fst.fst] = 0;
	//cout << rs1.fst.snd << " " << rs1.fst.fst << " " << rs1.snd << "\n";
	ppp o = dijkstra(rs1.fst.fst), s = dijkstra(rs1.fst.snd);
	//cout << o.fst.fst << " " << o.fst.snd << " " << o.snd.fst << " " << o.snd.snd << "\n";
	//cout << s.fst.fst << " " << s.fst.snd << " " << s.snd.fst << " " << s.snd.snd << "\n";
	if (o.fst.fst + 1 && s.fst.fst + 1)
	{
		if (o.fst.fst == s.fst.fst) 
		{
			if (o.snd.fst + 1) rs = min(rs, o.snd.snd + s.fst.snd);
			if (s.snd.fst + 1) rs = min(rs, o.fst.snd + s.snd.snd);
		}
		else {rs = o.fst.snd + s.fst.snd;}
	}
	for (int i = 0; i < n; i++)
	{
		if (special[i]) {pq.push({{0, i}, i});}
	}
	//cout << findShortestPair().fst.fst << " " <<findShortestPair().fst.snd << " " << findShortestPair().snd << "\n";
	rs = min(rs, rs1.snd + findShortestPair().snd);
	printf("%d\n", rs);
	return 0;
}

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