Shortest Routes I

input/code.cpp: In constructor 'Dijkstra::Dijkstra(std::vector<std::unordered_set<int> >, std::unordered_map<std::pair<int, int>, int, hashPair>)':
input/code.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::unordered_set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i<neighbors.size(); ++i){
      |                     ~^~~~~~~~~~~~~~~~~
input/code.cpp: In member function 'void Dijkstra::find(int)':
input/code.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::unordered_set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i<neighbors.size(); ++i){
      |                     ~^~~~~~~~~~~~~~~~~

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>


struct hashPair{
  
  size_t operator()(const std::pair<int, int>& p) const{
    return std::hash<int>{}(p.first) ^ std::hash<int>{}(p.second);
  }
};



// Dijkstra
struct Dijkstra {
  std::vector<std::unordered_set<int>> neighbors;
  std::unordered_map<std::pair<int, int>, int, hashPair> edgesDist;
  std::vector<int> dist;
  std::vector<int> prev;
  std::vector<int> vertices;
  Dijkstra(std::vector<std::unordered_set<int>> ne, std::unordered_map<std::pair<int, int>, int, hashPair> edgesDist):neighbors(ne), edgesDist(edgesDist){
    //Vertices
    vertices.resize(neighbors.size());
    dist.resize(neighbors.size());
    prev.resize(neighbors.size());
    for (int i = 0; i<neighbors.size(); ++i){
      vertices[i] = i;
    }
  }

  void find(int source){
    auto cmp = [&](int v1, int v2){
      return dist[v1] < dist[v2];
    };
    for (int i = 0; i<neighbors.size(); ++i){
      dist[i] = std::numeric_limits<int>::max();
      prev[i] = -1; //null
    }
    dist[source] = 0;

    std::multiset verts(vertices.begin(), vertices.end(), cmp);


    while (!verts.empty()){
      int u = *verts.cbegin();
      verts.erase(verts.begin());
      for (int ne : neighbors[u]){
        int alt_dist = dist[u] + edgesDist[{u, ne}];
        if (alt_dist<dist[ne]){
          dist[ne] = alt_dist;
          prev[ne] = u;
          if (auto it = verts.find(ne); it !=verts.end()){
            verts.erase(it);
            verts.insert(ne);
          };
        }
      }
    }
  }
};


int main(){
  int n, m;
  std::cin >> n >> m;
  std::vector<std::unordered_set<int>> neighbors(n);
  std::unordered_map<std::pair<int, int>, int, hashPair> edgesDist;

  for (int i = 0; i<m; ++i){
    int c1, c2, dist;
    std::cin >> c1 >> c2 >> dist;
    neighbors[c1-1].insert(c2-1);
    // neighbors[c2-1].push_back(c1-1);
    if (edgesDist.contains({c1-1, c2-1})){
      edgesDist[{c1-1, c2-1}] = std::min(dist, edgesDist[{c1-1, c2-1}]);
    } else {
      edgesDist[{c1-1, c2-1}] = dist;
    }
  }


  Dijkstra dij(neighbors, edgesDist);
  dij.find(0);

  for (int i = 0; i<n; ++i){
    std::cout << dij.dist[i] << " ";
  }
  std::cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: ACCEPTED