Submission #1176258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176258		Johan	Cyberland (APIO23_cyberland)	C++20	0 / 100	181 ms	317044 KiB

cyberland

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

const int MAX = 1e7 + 6;
const int LOG = 25;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int block = 333;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector < double > d(MAX, inf);
vector < vector < pair < int , int > > > adj(MAX);
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > pq;
void djk(int s){
  d[s] = 0;
  pq.push({d[s], s});
  while(pq.size()){
    int w = pq.top().first;
    int from = pq.top().second;
    pq.pop();
    if(w != d[from])  continue;
    for(pair < int , int > p : adj[from]){
      int we = p.first;
      int to = p.second;
      if(d[to] > d[from] + we){
        d[to] = d[from] + we;
        pq.push({d[to], to});
      } 
    }
  }
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
  int m = M, n = N, k = K, h = H;
  for(int i = 0; i < m; i++){
    adj[x[i]].push_back({c[i], y[i]});
    adj[y[i]].push_back({c[i], x[i]});
  }
  djk(0);
  double ans = d[h];
  return -1;
}
// signed main(){
//   int n, m, k, h;
//   cin >> n >> m >> k >> h;
//   vector < int > x(m);
//   vector < int > y(m);
//   vector < int > c(m);
//   vector < int > a(n);
//   for(auto &i : x)  cin >> i;
//   for(auto &i : y)  cin >> i;
//   for(auto &i : c)  cin >> i;
//   for(auto &i : a)  cin >> i;
//   cout << solve(n, m, k, h, x, y, c, a) << endl;
// }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3