Самый короткий путь Дэйкстры-Хакер-Рейн

Question

Я решал проблему - Самый короткий рейд Дейкстры 2. Вот link.

Учитывая, что граф содержит N узлов (обозначенных от 1 до N), где конкретный заданный узел S представляет начальную позицию S, а ребро между двумя узлами имеет заданную длину, которая может быть или не быть равной другим длинам в график.

Требуется вычислить кратчайшее расстояние от начальной позиции (узла S) до всех остальных узлов графика.

Примечание: Если узел недоступен, то расстояние, как предполагается, - 1.

Входной формат

Первая строка содержит, обозначающее количество тестов. Первая строка каждого тестового примера имеет два целых числа, обозначающие количество узлов в графе и обозначающее количество ребер в графе.

Следующие строки состоят из трех целых чисел, разделенных пробелами, где и обозначают два узла, между которыми существует неориентированный край, обозначает длину ребра между этими соответствующими узлами.

Последняя строка имеет целое число, обозначающее начальную позицию.

Ограничения

Если есть ребра между одной и той же парой узлов с различными весами, они должны рассматриваться как есть, как и кратных ребер.

Формат вывода

Для каждого из тестов, напечатать одну строку, состоящую пространство целых числа, обозначающие кратчайшее расстояние, отличных от начальной позиции в порядке возрастания их меток узлов.

Для недостижимых узлов напечатайте.

Пример ввода

1 
4 4 
1 2 24 
1 4 20 
3 1 3 
4 3 12 
1 

Пример вывода

24 3 15 

И вот мой код:

Класс Node

class Node implements Comparator<Node>{ 
    int cost, node; 
    Node(){} 
    Node(int node, int cost){ 
     this.node=node; 
     this.cost=cost; 
    } 
@Override 
public int compare(Node n1, Node n2){ 
    if(n1.cost<n2.cost)return -1; 
    else if(n1.cost>n2.cost)return 1; 
    return 0; 
    } 
} 
class Solution { 
// Working program using Reader Class 
static int adjmatrix[][]; 
static PriorityQueue<Node> pq; 
static boolean visited[]; 
static int distance[]; 
@SuppressWarnings("unchecked") 
static ArrayList<Map<Integer,Integer>> list; 


    static class Reader 
    { 
     final private int BUFFER_SIZE = 1 << 16; 
     private DataInputStream din; 
     private byte[] buffer; 
     private int bufferPointer, bytesRead; 

     public Reader() 
     { 
      din = new DataInputStream(System.in); 
      buffer = new byte[BUFFER_SIZE]; 
      bufferPointer = bytesRead = 0; 
     } 

     public Reader(String file_name) throws IOException 
     { 
      din = new DataInputStream(new FileInputStream(file_name)); 
      buffer = new byte[BUFFER_SIZE]; 
      bufferPointer = bytesRead = 0; 
     } 

     public String readLine() throws IOException 
     { 
      byte[] buf = new byte[64]; // line length 
      int cnt = 0, c; 
      while ((c = read()) != -1) 
      { 
       if (c == '\n') 
        break; 
       buf[cnt++] = (byte) c; 
      } 
      return new String(buf, 0, cnt); 
     } 

     public int nextInt() throws IOException 
     { 
      int ret = 0; 
      byte c = read(); 
      while (c <= ' ') 
       c = read(); 
      boolean neg = (c == '-'); 
      if (neg) 
       c = read(); 
      do 
      { 
       ret = ret * 10 + c - '0'; 
      } while ((c = read()) >= '0' && c <= '9'); 

      if (neg) 
       return -ret; 
      return ret; 
     } 

     public long nextLong() throws IOException 
     { 
      long ret = 0; 
      byte c = read(); 
      while (c <= ' ') 
       c = read(); 
      boolean neg = (c == '-'); 
      if (neg) 
       c = read(); 
      do { 
       ret = ret * 10 + c - '0'; 
      } 
      while ((c = read()) >= '0' && c <= '9'); 
      if (neg) 
       return -ret; 
      return ret; 
     } 

     public double nextDouble() throws IOException 
     { 
      double ret = 0, div = 1; 
      byte c = read(); 
      while (c <= ' ') 
       c = read(); 
      boolean neg = (c == '-'); 
      if (neg) 
       c = read(); 

      do { 
       ret = ret * 10 + c - '0'; 
      } 
      while ((c = read()) >= '0' && c <= '9'); 

      if (c == '.') 
      { 
       while ((c = read()) >= '0' && c <= '9') 
       { 
        ret += (c - '0')/(div *= 10); 
       } 
      } 

      if (neg) 
       return -ret; 
      return ret; 
     } 

     private void fillBuffer() throws IOException 
     { 
      bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
      if (bytesRead == -1) 
       buffer[0] = -1; 
     } 

     private byte read() throws IOException 
     { 
      if (bufferPointer == bytesRead) 
       fillBuffer(); 
      return buffer[bufferPointer++]; 
     } 

     public void close() throws IOException 
     { 
      if (din == null) 
       return; 
      din.close(); 
     } 
    } 
    //////////////////////////////////////////////// 
    public static void initialize(int n){ 
     // adjmatrix=new int[n+1][n+1]; 
     visited=new boolean[n+1]; 
     distance=new int[n+1]; 
     list=new ArrayList<>(n+1); 
     pq=new PriorityQueue<>(new Node()); 
     for(int i=0; i<n+1; ++i)distance[i]=Integer.MAX_VALUE; 
    } 

////////////////////////////////////////////// 
public static void shortestPath(int s){ 
    // int length=adjmatrix.length; 
    int min_node; 
    visited[s]=true; 
    distance[s]=0; 
    pq.add(new Node(s,0)); 
    while(!pq.isEmpty()){ 
     min_node=pq.remove().node; 
     visited[min_node]=true; 
     updateDistance(min_node); 
    } 
} 
/////////////////////////////////////////////// 
//Using adjlist 
private static void updateDistance(int s){ 
    Map<Integer,Integer> current=list.get(s); 
    // Iterator itr=current.entrySet().iterator(); 
    for(Map.Entry<Integer, Integer> entry:current.entrySet()){ 
     int node=entry.getKey(); 
     int cost=entry.getValue(); 
     if(!visited[node]){ 

       distance[node]=Math.min(cost+distance[s], distance[node]); 
       pq.add(new Node(node,distance[node])); 

     } 
    } 

} 

//////////////////////////////////////////////////////////////// 
    public static void main(String []args)throws IOException{ 
     Reader r=new Reader(); 
    //StringBuilder sb = new StringBuilder(); 


    int T=r.nextInt(), N, M; 
    for(int caseNo=1; caseNo<=T; ++caseNo){ 
     N=r.nextInt(); 
     //initialization 
     initialize(N); 
     //initialization of adjacecny matrix 



     M=r.nextInt(); 
     //list=new ArrayList<>(N+1); 
     for(int i=1; i<=N+1; ++i)list.add(new HashMap<Integer, Integer>()); 

     for(int j=1; j<=M; ++j){ 

       int node1=r.nextInt(); 
       int node2=r.nextInt(); 
       int distance=r.nextInt(); 

       if(list.get(node1).get(node2)!=null){ 
        int temp=list.get(node1).get(node2); 
        if(temp<distance)continue; 
       } 

       list.get(node1).put(node2,distance); 
       list.get(node2).put(node1, distance); 

     } 

     //end of graph initialization as a hybrid of adjmatrix and adjlist 

     int s=r.nextInt(); 
     shortestPath(s); 

     for(int i=1; i<=N; ++i)if(i!=s)System.out.print(((distance[i]==Integer.MAX_VALUE)?-1:distance[i])+" "); 
     System.out.println(); 
    }//end of test cases loop[ 
} 
} 

Извиняюсь за длинный код и вопрос. Моя программа работает только для тестового примера. В остальном он начинается правильно, но к концу ввода он заканчивает тем, что дает другой ответ. При необходимости я могу вставить копию ожидаемого ввода и вывода. Насколько я могу судить, это, вероятно, связано с тем, как я обрабатываю случай с несколькими неориентированными ребрами. Я держу только меньший край.

P.S.-Дает правильные значения сейчас, но скорость не достаточно высокая.Любые предложения по оптимизации приветствуются

Answer 1

На первый взгляд ваш код кажется правильным (хотя я не эксперт в Java).

Ниже мой код в качестве ссылки (может дать вам идею), & вот ссылка на код в моем GitHub Dijkstra hackerrank

На самом деле это было принято с версией Queue (вы не должны . реализовать его с minHeap - хотя minHeap версия более правильно - о (Е войти V) вместо O (V^2)

Вот версия очереди: Dijkstra queue version

#include <iostream> 
#include <vector> 
#include <utility> 
#include <limits> 
#include <memory> 
#include <map> 
#include <set> 
#include <queue> 
#include <stdio.h> 


using namespace std; 
using vi = vector<int>; 
using ii = pair<int, int>; 
using vii = vector<ii>; 
const int max_int = 1 << 20; //numeric_limits<int>::max(); 


class Graph{ 
public: 
    Graph(int nodes = 3000, int edges = 3000*3000/2): 
     nodes_(nodes+1), 
     edges_(edges), 
     dist_(nodes+1, max_int), 
     adjList_(nodes+1), 
     in_queue_(nodes+1, 0) 
    { 
    } 
    ~Graph() {} 
    void addEdge(int from, int to, int w) { 

     adjList_[from].emplace_back(ii(w, to)); 
     adjList_[to].emplace_back(ii(w, from)); 
    } 
    vii getNeighbours(int n) { 
     return adjList_[n]; 
    } 
    void dijkstra(int src); 

private: 
    vi dist_; 
    vector<vii> adjList_; 
    int nodes_; 
    int edges_; 
    int src_; 
    void print(int node); 
    vi in_queue_; 
    // queue<int> q_; 
    std::priority_queue<ii, vii, greater<ii>> q_; 
}; 

void Graph::dijkstra(int src) 
{ 
    src_ = src; 
    dist_[src] = 0; 
    q_.push(make_pair(0, src)); in_queue_[src_] = 1; 
    while(!q_.empty()) { 
     auto front = q_.top(); q_.pop(); 
     int d = dist_[front.second], u = front.second; 
     in_queue_[u] = 0; 
      for(int i = 0 ; i < (int)adjList_[u].size(); ++i) { 
       auto v = adjList_[u][i]; 
       if(dist_[v.second] > dist_[u] + v.first) { 
        dist_[v.second] = dist_[u] + v.first; 
        if(!in_queue_[v.second]) { 
         q_.push(make_pair(dist_[v.second], v.second)); 
         in_queue_[v.second] = 1; 
        } 
       } 
      } 
    } 

    for(int i = 1; i < nodes_; ++i) { 
     if(i == src_) { 
      continue; 
     } 
     if(dist_[i] == max_int) { 
      cout << "-1" << " "; 
     } 
     else{ 
      cout << dist_[i] << " "; 
     } 
    } 
    cout << endl; 
} 



int main(){ 
    std::ios::sync_with_stdio(false); 
    int t; 
    cin >> t; 
    for(int a0 = 0; a0 < t; a0++){ 
     int n; 
     int m; 
     cin >> n >> m; 
     unique_ptr<Graph> g(new Graph(n,m)); 
     for(int a1 = 0; a1 < m; a1++){ 
      int x; 
      int y; 
      int r; 

      cin >> x >> y >> r; 
      g->addEdge(x, y, r); 
     } 
     int s; 
     cin >> s; 
     //scanf("%d", &s); 
     g->dijkstra(s); 
    } 
    return 0; 
}