제출 #1283493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283493		Faisal_Saqib	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	2 ms	2616 KiB

crocodile

#include "crocodile.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int QK=1e5+100,inf=1e9;
int n,k;
ll dist[QK],sp[QK];
ll dp[QK][5];
vector<pair<int,int>> adj[QK];
void dykstra(){
  for(int i=0;i<=n;i++)
  {
    dp[i][0]=inf;
    dp[i][1]=inf;
    dist[i]=inf;
  }
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
  for(int j=0;j<k;j++){
    dist[sp[j]]=0;
    pq.push({0,sp[j]});
  }
  while(!pq.empty()){
    auto [d,u]=pq.top();pq.pop();
    if(d>dist[u])continue;
    for(auto [v,w]:adj[u]){
      if(dist[v]>dist[u]+w){
        dist[v]=dist[u]+w;
        pq.push({dist[v],v});
      }
    }
  }
}
void calculate(){
  // ord of {(dist,node)}
  // dp[node][0] = min(dist[nei][0])
  // dp[node][1] = 2min(dist[nei][0])
  vector<pair<ll,int>> ord;
  for(int i=0;i<n;i++)
    ord.push_back({dist[i],i});
  sort(ord.begin(),ord.end());
  for(auto [d,u]:ord){
    auto it=lower_bound(sp,sp+k,u);
    if(it!=sp+k && *it==u){
      // cout<<u<<" special "<<endl;
      dp[u][0]=0;
      dp[u][1]=0;
      continue;
    }
    vector<ll> curp;
    for(auto [v,w]:adj[u]){
      curp.push_back(dp[v][0]+w);
      // int cur=dp[v][0]+w;
      // cout<<"Adj "<<u<<' '<<cur<<endl;

    }
    for(int i=1;i<curp.size();i++)
    {
      ll cur=curp[i];
            if(cur<dp[u][0]){
        dp[u][1]=dp[u][0];
        dp[u][0]=cur;
      }
      else if(cur<dp[u][1]){
        dp[u][1]=cur;
      }
    }
    // cout<<"For "<<u<<": dp0="<<dp[u][0]<<" dp1="<<dp[u][1]<<endl;
  }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  n=N,k=K;
  for(int i=0;i<K;i++)
    sp[i]=P[i];
  sort(sp,sp+K);
  for(int i=0;i<M;i++){
    int u=R[i][0],v=R[i][1],l=L[i];
    adj[u].push_back({v,l});
    adj[v].push_back({u,l});
  }
  dykstra();
  calculate();
  return dp[0][0];
}

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