oj.uz

Submission #335450

# Submission time Handle Problem Language Result Execution time Memory
335450 2020-12-12T16:47:39 Z codebuster_10 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
using namespace std ;
#define f(i,a,b) for(int i=a;i<b;++i)

const int64_t INF = 1e12 ; 
int travel_plan(int N, int M, int R[][2],int L[], int K,int P[]){
  vector< vector< array<int,2> > > g(N) ;
  f(i,0,M){
    int u = R[i][0], v = R[i][1], w = L[i] ;
    g[u].push_back({v, w}) ;
    g[v].push_back({u, w}) ;
  }
  vector< array<int64_t,2> > best(N, {INF, INF}) ;
  f(i,0,K) best[P[i]][0] = best[P[i]][1] = 0 ;
  priority_queue< pair<int64_t,int> > p ;
  f(i,0,N){
    p.push({-best[i][1],i}) ;
  }
  while(int(p.size())){
    int i = p.top().second ;
    p.pop() ;
    for(auto [j,w]:g[i]){
      int NewDis = w + best[i][1] ;
      if(NewDis < best[j][0]){
        best[j][1] = best[j][0] ;
        best[j][0] = NewDis ;
        p.push({-best[j][1],j}) ;
      }else if(NewDis < best[j][1]){
        best[j][1] = NewDis ;
        p.push({-best[j][1],j}) ;
      }
    }
  }
  return int(best[0][1]) ;
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -