Submission #891763

#	Time	Username	Problem	Language	Result	Execution time	Memory
891763		vjudge1	Relay Marathon (NOI20_relaymarathon)	C++14	25 / 100	1211 ms	141720 KiB

RelayMarathon

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(a) (a).begin(), (a).end()

const int N=1e5+1;
int n, m, k, dd[N];
int dist[N], par[N], d1[N], d2[N];
vector<pair<int, int>> g[N];

pair<pair<int, int>, pair<int, int>> dijkstra(int root, int d[]){
   memset(d, 0, sizeof(int)*N);
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   d[root]=0;
   pq.emplace(d[root], root);
   pair<pair<int, int>, pair<int, int>> ans={{1e18, -1}, {1e18, -1}};
   while (pq.size()){
      int u=pq.top().second, f=pq.top().first;
      pq.pop();
      if (d[u]!=f) continue;
      if (dd[u]){
         if (ans.first.first>dist[u]){
            ans.second=ans.first;
            ans.first={dist[u], u};
         }else ans.second=min(ans.second, {dist[u], u});
      }
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         if (d[v]>d[u]+w){
            d[v]=d[u]+w;
            pq.emplace(d[v], v);
         }
      }
   }
   return ans;
}

pair<int, pair<int, int>> dijkstra(vector<int> root){
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   memset(dist, 0x3f, sizeof dist);
   for (int x:root){
      dist[x]=0; par[x]=x;
      pq.emplace(dist[x], x);
   }
   pair<int, pair<int, int>> best={-1, {-1, -1}};
   while (pq.size()){
      int u=pq.top().second, d=pq.top().first; pq.pop();
      if (dist[u]!=d) continue;
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         if (par[u]!=par[v]){
            if (best.first==-1) best={dist[u]+dist[v]+w, {par[u], par[v]}};
            else best=min(best, {dist[u]+dist[v]+w, {par[u], par[v]}});
         }
         if (dist[v]>dist[u]+w){
            dist[v]=dist[u]+w;
            par[v]=par[u];
            pq.emplace(dist[v], v);
         }
      }
   }
   return best;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m >> k;
   for (int i=1; i<=m; ++i){
      int u, v, w; cin >> u >> v >> w;
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
   }
   vector<int> v(k);
   for (int &i:v) cin >> i, dd[i]=1;
   auto best1=dijkstra(v);
   int t1=best1.second.first, t2=best1.second.second;
   v.erase(find(all(v), t1));
   v.erase(find(all(v), t2));
   dd[t1]=dd[t2]=0;
   auto g1=dijkstra(t1, d1);
   auto g2=dijkstra(t2, d2);
   auto best2=dijkstra(v);
   int ans=best1.first+best2.first;
   if (g1.first.second!=-1 && g2.first.second!=-1 && g1.first.second!=g2.first.second){
      ans=min(ans, g1.first.first+g2.first.first);
   }
   if (g1.first.second!=-1 && g2.second.second!=-1 && g1.first.second!=g2.second.second){
      ans=min(ans, g1.first.first+g2.second.first);
   }
   if (g1.second.second!=-1 && g2.first.second!=-1 && g1.second.second!=g2.first.second){
      ans=min(ans, g1.second.first+g2.first.first);
   }
   cout << ans;
   return 0;
}

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