Submission #903864

#	Time	Username	Problem	Language	Result	Execution time	Memory
903864		pcc	Relay Marathon (NOI20_relaymarathon)	C++14	25 / 100	2654 ms	135672 KiB

RelayMarathon

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>


const int inf = 1e9+10;
const int mxn = 1e5+10;
vector<pii> paths[mxn];
vector<pii> dist[mxn];
priority_queue<tiii,vector<tiii>,greater<tiii>> pq;
ll N,M,K;
int sp[mxn];
vector<pair<int,pii>> v;

void DIJKSTRA(){
	for(int i = 1;i<=K;i++){
		int now = sp[i];
		dist[now].push_back(make_pair(0,now));
		sort(dist[now].begin(),dist[now].end());
		pq.push(make_tuple(0,now,now));
	}
	while(!pq.empty()){
		int d = get<0>(pq.top()),now = get<1>(pq.top()),f = get<2>(pq.top());
		pq.pop();
		bool flag = false;
		for(auto &i:dist[now]){
			if(i == make_pair(d,f))flag = true;
		}
		if(!flag)continue;
		for(auto nxt:paths[now]){
			if(dist[nxt.fs].size()<5||dist[nxt.fs].back().fs>=d+nxt.sc){
				bool can = true;
				int idx = -1;
				for(int i = 0;i<dist[nxt.fs].size();i++){
					if(dist[nxt.fs][i].sc == f){
						if(dist[nxt.fs][i].fs<=d+nxt.sc)can = false;
						else idx = i;
					}
				}
				if(!can)continue;
				if(idx == -1){
					dist[nxt.fs].push_back({d+nxt.sc,f});
				}
				else{
					dist[nxt.fs][idx].fs = d+nxt.sc;
				}
				sort(dist[nxt.fs].begin(),dist[nxt.fs].end());
				pq.push(make_tuple(d+nxt.sc,nxt.fs,f));
				while(dist[nxt.fs].size()>5)dist[nxt.fs].pop_back();
			}
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>K;
	for(int i = 1;i<=M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		paths[a].push_back(make_pair(b,c));
		paths[b].push_back(make_pair(a,c));
	}
	for(int i = 1;i<=K;i++)cin>>sp[i];
	DIJKSTRA();
	/*
	for(int i = 1;i<=K;i++){
		cout<<sp[i]<<":";for(auto &j:dist[sp[i]])cout<<j.fs<<','<<j.sc<<' ';cout<<endl;
	}

   */
	for(int i = 1;i<=K;i++){
		for(auto &j:dist[sp[i]]){
			if(j.sc == sp[i])continue;
			v.push_back(make_pair(j.fs,make_pair(sp[i],j.sc)));
		}
	}
	sort(v.begin(),v.end());
	for(auto &i:v){
		if(min(i.sc.fs,i.sc.sc) != 1){
			cout<<i.fs+1;
			return 0;
		}
	}
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'void DIJKSTRA()':
RelayMarathon.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0;i<dist[nxt.fs].size();i++){
      |                   ~^~~~~~~~~~~~~~~~~~~~

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