Submission #333013

#	Time	Username	Problem	Language	Result	Execution time	Memory
333013		Cantfindme	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	3052 ms	204216 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 100010;

typedef pair<int,pi> pp;
#define p(x,y,z) pp(x,pi(y,z))

int dist[maxn],col[maxn];
int special[maxn];
int n,m,k;

vector <int> specials;
vector <pi> adjlist[maxn];

int A = -1, B = -1;

int test(int excludea, int excludeb) {
	memset(dist,-1,sizeof dist);
	memset(col,-1,sizeof col);
	priority_queue <pi,vector<pi>,greater<pi>> pq;
	
	for (auto cur: specials) {
		if (cur == excludea or cur == excludeb) continue;
		pq.push(pi(0,cur));
		dist[cur] = 0;
		col[cur] = cur;
	}
	
	while (!pq.empty()) {
		pi cur = pq.top(); pq.pop();
		int x = cur.s, d = cur.f;
		//cout << "GO: " << x << " " << d << "\n";
		
		if (dist[x] != d) continue;
		
		for (auto i: adjlist[x]) {
			if (dist[i.f] == -1 or dist[i.f] > d + i.s) {
				dist[i.f] = d + i.s;
				col[i.f] = col[x];
				pq.push(pi(dist[i.f],i.f));
			}
		}
	}
	
	//cout << "NEW: " << excludea << " " << excludeb << "\n";
	//for (int i =1;i<=n;i++) {
		//cout << i << " " << dist[i] << " " << col[i] << "\n";
	//}
	
	pp ans = p(LLONG_MAX/2,0,0);
	
	for (int i = 1; i <= n;i++) {
		for (auto u: adjlist[i]) {
			if (col[i] != col[u.f] and col[i] != -1 and col[u.f] != -1) {
				if (dist[u.f] + dist[i] + u.s < ans.f) {
					ans = p(dist[u.f] + dist[i] + u.s, col[u.f], col[i]);
				}
			}
		}
	}
	
	//cout << "ANS: " << ans.f << " " << ans.s.f << " " << ans.s.s << "\n";
	
	if (excludea == -1 or excludeb == -1) {
		if (A == -1 and B == -1) {
			A = ans.s.f; B = ans.s.s;
		}
		return ans.f + test(ans.s.f, ans.s.s);
	} else return ans.f;
}

int32_t main() {
	FAST
	cin >> n >> m >> k;
	for (int i =0;i<m;i++) {
		int a,b,c; cin >> a >> b >> c;
		adjlist[a].push_back(pi(b,c));
		adjlist[b].push_back(pi(a,c));
	}
	
	for (int i =0;i<k;i++) {
		int x; cin >> x;
		special[x] = 1;
		specials.push_back(x);
	}
	int rans = LLONG_MAX/2;
		
	rans = min(rans,test(-1,-1));
	rans = min(rans,test(A,-1));
	rans = min(rans,test(B,-1));
	cout << rans;
}

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