Submission #676492

#	Time	Username	Problem	Language	Result	Execution time	Memory
676492		penguin133	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	1776 ms	203260 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second

priority_queue<pi, vector<pi>, greater<pi> > pq;
int n,m,k;
vector<pi>v[100005];
int A[100005], dist[100005], stor[100005], stor2[100005], dist2[100005], dist3[100005], dist4[100005];
vector<pi>v2;

main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin >> x >>y >> z;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
	}
	for(int i=1;i<=n;i++)dist[i] = dist2[i] = dist3[i] = dist4[i] = 1e9;
	for(int i=1;i<=k;i++){
		cin >> A[i];
		pq.push({0, A[i]}), dist[A[i]] = 0, stor[A[i]] = i;
	}
	while(!pq.empty()){
		int x = pq.top().se, y = pq.top().fi;
		pq.pop();
		if(dist[x] < y)continue;
		for(auto a : v[x]){
			int i = a.fi, j = a.se;
			if(dist[i] > j + y)dist[i] = j + y, pq.push({j+y, i}), stor[i] = stor[x];
		}
	}
	int ans = 1e18;
	int in, in2;
	for(int i=1;i<=n;i++){
		for(auto j : v[i]){
			if(stor[i] != stor[j.fi]){
				if(ans > dist[i] + dist[j.fi] + j.se)ans = dist[i] + dist[j.fi] + j.se, in = stor[i], in2 = stor[j.fi];
			}
		}
	}
	for(int i=1;i<=k;i++){
		if(i == in || i == in2)continue;
		pq.push({0, A[i]}), dist2[A[i]] = 0, stor2[A[i]] = i;
	}
	
	
	while(!pq.empty()){
		int x = pq.top().se, y = pq.top().fi;
		pq.pop();
		if(dist2[x] < y)continue;
		for(auto a : v[x]){
			int i = a.fi, j = a.se;
			if(dist2[i] > j + y)dist2[i] = j + y, pq.push({j+y, i}), stor2[i] = stor2[x];
		}
	}
	int ans2 = 1e18;
	for(int i=1;i<=n;i++){
		for(auto j : v[i])if(stor2[i] != stor2[j.fi])ans2 = min(ans2, dist2[i] + dist2[j.fi] + j.se);
	}
	pq.push({0, A[in]});
	while(!pq.empty()){
		int x = pq.top().se, y = pq.top().fi;
		pq.pop();
		if(dist3[x] < y)continue;
		for(auto a : v[x]){
			int i = a.fi, j = a.se;
			if(dist3[i] > j + y)dist3[i] = j + y, pq.push({j+y, i});
		}
	}
	pq.push({0, A[in2]});
	while(!pq.empty()){
		int x = pq.top().se, y = pq.top().fi;
		pq.pop();
		if(dist4[x] < y)continue;
		for(auto a : v[x]){
			int i = a.fi, j = a.se;
			if(dist4[i] > j + y)dist4[i] = j + y, pq.push({j+y, i});
		}
	}
	int ans3 = 1e18;
	int in3, mini = 1e18;
	
	for(int i=1;i<=k;i++){
		if(i == in || i == in2)continue;
		v2.push_back({dist3[A[i]], A[i]});
	}
	sort(v2.begin(), v2.end());
	for(int i=1;i<=k;i++){
		if(i == in || i == in2)continue;
		if(A[i] == v2[0].se){
			ans3 = min(ans3, v2[1].fi + dist4[v2[0].se]);
		}
		else ans3 = min(ans3, v2[0].fi + dist4[A[i]]);
	}
	//cout << ans + ans2 << " " << ans3 << " " << in << " " << in2 << '\n';
	cout << min(ans + ans2, ans3);
}

Compilation message (stderr)

RelayMarathon.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:88:6: warning: unused variable 'in3' [-Wunused-variable]
   88 |  int in3, mini = 1e18;
      |      ^~~
RelayMarathon.cpp:88:11: warning: unused variable 'mini' [-Wunused-variable]
   88 |  int in3, mini = 1e18;
      |           ^~~~
RelayMarathon.cpp:49:19: warning: 'in2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   if(i == in || i == in2)continue;
      |                 ~~^~~~~~
RelayMarathon.cpp:49:8: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   if(i == in || i == in2)continue;
      |      ~~^~~~~

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