Submission #1161081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161081		Newtonabc	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1 ms	2624 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int NN=1e5+10;
vector<pair<ll,int>> adj[NN];
ll d[NN],sd[NN],pd[NN],psd[NN];
ll sew[NN];
//second edge weight to go to i
bool vs[NN],out[NN];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int i=0;i<N;i++) d[i]=sd[i]=LLONG_MAX;
  for(int i=0;i<M;i++){
    int u=R[i][0],v=R[i][1];
    adj[u].push_back({v,L[i]});
    adj[v].push_back({u,L[i]});
  }
  //multiple source shortest path
  for(int i=0;i<K;i++) d[P[i]]=0,q.push({0,P[i]}),out[P[i]]=true;
  while(!q.empty()){
    int u=q.top().second;
    q.pop();
    for(auto [v,w]:adj[u]){
      if(d[u]+w<d[v]){
        d[v]=d[u]+w;
        pd[v]=u;
        q.push({d[v],v});
      }
    }
  }
  // for(int i=0;i<N;i++) cout<<d[i] <<" ";
  // cout<<"\n";
  /*for(int i=0;i<M;i++){
    int u=R[i][0],v=R[i][1];
    ll w=L[i];
    //u->v
    if(d[u]+w<=sd[v]){
      if(pd[v]!=u){
        sd[v]=d[u]+w;
        psd[v]=u,sew[v]=w;
      }
    }
    //v->u
    if(d[v]+w<=sd[u]){
      if(pd[u]!=v){
        sd[u]=d[v]+w;
        psd[u]=v,sew[u]=w;
      }
    }
  }*/
  int now=0;
  ll ans=0;
  for(int i=0;i<N;i++) vs[i]=false;
  while(!out[now]){
    ll mn=LLONG_MAX,wi;
    int nxt;
    //cout<<now <<" " <<ans <<" ";
    vs[now]=true;
    for(auto [v,w]:adj[now]){
      if(vs[v]) continue;
      if(v==pd[now]) continue;
      if(mn>w+d[v]){
        mn=w+d[v];
        nxt=v;
        wi=w;
      }
    }
    now=nxt;
    ans+=wi;
  }
  return ans;
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11