Dijkstra's Shortest Path-HackerRank

Question

私はこの問題を解決していました - Dijkstraの最短到達範囲2。ここにはlinkがあります。

特定の所与のノードSが開始位置Sを表し、2つのノード間のエッジが所与の長さであり、他の長さと等しくてもなくてもよいN個のノード（1からNとラベル付けされる）グラフ。

グラフの開始位置（ノードS）から他のすべてのノードまでの最短距離を計算する必要があります。

注：ノードが到達不能である場合、距離は次のように想定している - 1

入力形式

最初の行は、テストケースの数を表す、含ま。 各テストケースの最初の行には、グラフのノード数を示す2つの整数があり、グラフのエッジ数を示します。

次の行はそれぞれ、これらの対応するノード間のエッジの長さを示し、無向エッジが存在する間に2つのノードを表す3スペースで区切られた整数から成ります。

最後の行には、開始位置を示す整数があります。

制約

異なる重みを持つノードの同じ対の間にエッジが存在する場合、それらは複数のエッジのような、あるとして考えられるべきです。テストケースの各々について

出力フォーマット

、そのラベルの昇順で開始位置から以外のノードの最短距離を表す空間分離整数からなる単一の行を印刷します。

到達不能なノードについては、印刷してください。

サンプル入力

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バージョンがより正確であるが、 - O（E 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; 
}