Submission #951286

#	Time	Username	Problem	Language	Result	Execution time	Memory
951286		NourWael	Relay Marathon (NOI20_relaymarathon)	C++17	42 / 100	1069 ms	184936 KiB

RelayMarathon

#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 1e5+5;
vector<pair<int,int>> adj[mxN];
vector<int> spe;
bool is[mxN], vis[mxN];
int dist[505][505], cur[mxN], come[mxN];
int n; 
vector<pair<int,int>> lis[mxN];

int solve () {

   memset(vis,0,sizeof vis);
   for(int j=1; j<=n; j++) cur[j] = 1e18;
   priority_queue<pair<int,pair<int,int>>> q;
   for(auto it:spe) { q.push({0,{it, it}}); cur[it] = 0; come[it] = it;}
   int ans = 1e18;
   while(q.size()) {
     int node = q.top().second.first, from = q.top().second.second, d = -(q.top().first);
     q.pop();

     if(vis[node]) continue;
     vis[node] = 1;

     for(auto it:adj[node]) {
      if(come[it.first]!=from) ans = min (ans, d+it.second+cur[it.first]);
      if(cur[it.first]<=d+it.second) continue;
      cur[it.first] = d+it.second;
      come[it.first] = from;
      q.push({-(d+it.second), {it.first,from}});
     }

   }

   return ans;
}

void solve2 ( int i , int e1, int e2, bool f) {
 
   memset(vis,0,sizeof vis);
   for(int j=1; j<=n; j++) cur[j] = 1e18;
   priority_queue<pair<int,int>> q;
   q.push({0,i});
   
   while(q.size()) {
     int node = q.top().second, d = -(q.top().first);
     q.pop();
     if(vis[node]) continue;
     vis[node] = 1;
     for(auto it:adj[node]) {
      if(cur[it.first]<=d+it.second) continue;
      cur[it.first] = d+it.second;
      q.push({-(d+it.second), it.first});
     }
   }
 
   for(int j=1; j<=n; j++) { 
      dist[i][j] = cur[j];
      if(is[j] && is[i]) lis[i].push_back({dist[i][j],j});
   }
   sort(lis[i].begin(),lis[i].end());
}

signed main() {
  
  ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
 
   int m,k; cin>>n>>m>>k;
   for(int i=0; i<m; i++) {
      int x,y,c; cin>>x>>y>>c;
      adj[x].push_back({y,c}), adj[y].push_back({x,c});
   }
   
   for(int i=0; i<k; i++) {
      int x; cin>>x;
      is[x] = 1;
      if(x!=1 && x!=2 && n>500) spe.push_back(x);
   }
   
   if(n>500) cout<<solve()+1;
   else {
     for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j] = 1e18; 
     for(int i=1; i<=n; i++) solve2(i, 0, 0, 0);
     int ans = 1e18;
     for(int i=1; i<=n; i++) {
        if(!is[i]) continue;
        for(int j=1; j<=n; j++) {
           if(!is[j] || j==i) continue;
           for(int h=1; h<=n; h++) {
              if(!is[h] || h==i || h==j) continue;
              for(int ind=0; ind<min(5ll,(int)lis[h].size()); ind++) {
               if(lis[h][ind].second!=i && lis[h][ind].second!=j && lis[h][ind].second!=h &&  lis[h][ind].first+dist[i][j]<ans){
                 ans =  lis[h][ind].first+dist[i][j];
               }
              }
           }
        }
     }
     cout<<ans;
   }

   return 0;
}
/*
7 6 4
1 2 1
7 3 1
3 4 2
4 5 3
5 6 5
6 3 4
1 2 5 7
*/

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