제출 #1180143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180143		adriines06	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	293 ms	56852 KiB

crocodile

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

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  int n=N,m=M,k=K;
  vector<pair<int,int>>adj;
  vector<vector<pair<int,int>>>g(n);

  priority_queue<pair<int,int>>pq;
  vector<pair<int,int>>dis(n,pair<int,int>{1e9+2,1e9+2});
  vector<bool>vis(n,false);

  for(int i=0;i<m;i++){
    int a=R[i][0],b=R[i][1]; 
    adj.push_back({a,b});
  }
  for(int i=0;i<m;i++){
    int w=L[i]; 
    g[adj[i].first].push_back({adj[i].second,w});
    g[adj[i].second].push_back({adj[i].first,w});
  }
  for(int i=0;i<k;i++){
    int x=P[i];
    dis[x].first=dis[x].second=0;
    pq.push({0,x});
  }
  while(!pq.empty()){
    int u=pq.top().second;
    pq.pop();
    if(vis[u]) continue;
    else vis[u]=1;
    for(auto p : g[u]){ 
      int w=p.second;int v=p.first;
      if(w==0) continue;
      if(dis[u].second+w<dis[v].first){ 
        dis[v].second=dis[v].first;
        dis[v].first=dis[u].second+w;

        pq.push({-dis[v].second,v});
      }
      else if(dis[v].first!=0 && dis[u].second+w<dis[v].second){
        dis[v].second=dis[u].second+w;

        pq.push({-dis[v].second,v});
      }
        
    }

  }
  return dis[0].second;
}

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