oj.uz

Submission #899688

# Submission time Handle Problem Language Result Execution time Memory
899688 2024-01-06T21:25:26 Z lalig777 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 4444 KB 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include "crocodile.h"
using namespace std;

const int INF=1e9+1;

int travel_plan(int N, int M, int R[][2], int S[], int K, int P[]){
  vector<vector<pair<int,int>>> listaAdy(N);
  for (int i=0; i<M; i++){
    listaAdy[R[i][0]].push_back(make_pair(R[i][1], S[i]));
    listaAdy[R[i][1]].push_back(make_pair(R[i][0], S[i]));
  }
  vector<pair<int,int>> dist(N, make_pair(INF, INF));
  priority_queue<pair<int, int>>pq;
  for (int i=0; i<K; i++){
    dist[P[i]].first=0;
    dist[P[i]].second=0;
    pq.push(make_pair(0, P[i]));
    while (!pq.empty()){
      int u=pq.top().second;
      int d=-pq.top().first;
      pq.pop();
      if (dist[u].second<d) continue;
      if (dist[u].first<=d) dist[u].second=d;
      else{
        dist[u].second=dist[u].first;
        dist[u].first=d;
      }
      if (dist[u].second==INF) continue;
      for (auto vec: listaAdy[u]){
        int v=vec.first;
        int c=vec.second;
        int dact=dist[u].second+c;
        if(dist[v].second>dact){
          dist[v].second=dact;
          if (dist[v].second<dist[v].first){
            dist[v].second=dist[v].first;
            dist[v].first=dact;
          }pq.push(make_pair(-dist[v].second, v));
        }
      }
    }
  }if (dist[0].second==INF) return -1;
  return dist[0].second;
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -