Dijkstra의 최단 경로 - HackerRank

Question

Dijkstra의 Shortest Reach 2 문제를 해결하고있었습니다. 여기에 link이 있습니다.

주어진 주어진 노드 S가 시작 위치 S를 나타내고 두 노드 사이의 에지가 주어진 길이 인 N 개의 노드 (1에서 N으로 레이블링 됨)로 구성된 그래프가 주어진다면, 이는 다른 길이와 같을 수도 있고 같지 않을 수도 있습니다. 그래프.

시작 위치 (노드 S)에서 그래프의 다른 모든 노드까지의 최단 거리를 계산해야합니다.

참고 : 노드가 도달 할 수없는 경우의 거리로 간주 - 테스트 케이스의 수를 나타내는, 1

입력 포맷

첫 번째 라인에 포함. 각 테스트 케이스의 첫 번째 줄에는 그래프의 노드 수를 나타내는 두 개의 정수가 있으며 그래프의 가장자리 수를 나타냅니다.

다음 행은 각각 3 개의 공백으로 구분 된 정수로 구성되며, 여기서는 무 방향성 모서리가있는 두 노드를 나타내며 해당 노드 사이의 모서리 길이를 나타냅니다.

마지막 줄에는 시작 위치를 나타내는 정수가 있습니다.

제약

다른 가중치와 동일한 노드 쌍 사이에 에지가있는 경우, 그들은 여러 에지 등과 IS 고려하여야한다. 테스트 케이스 각각에 대해

출력 형식

그들의 라벨의 증가하는 순서로 시작 위치에서보다 다른 노드의 최단 거리를 나타내는 공간 분리 정수 이루어진 단일 라인을 출력한다.

연결할 수없는 노드의 경우 인쇄하십시오.

샘플 입력

여기 샘플 출력

24 3 15 

그리고

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

내 코드입니다 :

노드 클래스

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

언뜻보기에 코드가 정확합니다 (비록 내가 자바 전문가는 아니지만). 다음은

은 (당신에게 아이디어를 줄 수 있음), 여기 & 내 GitHub의에서 코드에 대한 링크입니다 Dijkstra hackerrank

사실

가 대기열 버전으로 접수있어 (당신이없는 참고 자료로 내 코드입니다 . 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; 
}