제출 #1179889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179889		adriines06	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	0 ms	324 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<int>>g(n,vector<int>(n,0));

  priority_queue<pair<int,int>>pq;
  vector<pair<int,int>>dis(n,pair<int,int>{1e9+5,1e9+5});
  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][adj[i].second]=w;
    g[adj[i].second][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(int v=0;v<n;v++){ 
      int w=g[u][v];
      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].first,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: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11