[백준][Java] 1753번 최단경로 (dijkstra)

[백준][Java] 1753번 최단경로 (dijkstra)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; public class Main { private static BufferedReader br = new BufferedReader( new InputStreamReader( System . in )); private static BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System . out )); static List < Node > NodeList; static final int INF = 300000 * 10 * 2 ; private static void dijkstra( int K) { PriorityQueue < Node > q = new PriorityQueue < > ( (a,b) - > a.getMinDist() - b.getMinDist() ); NodeList.get(K).setMinDist( 0 ); q.offer(NodeList.get(K)); while ( ! q.isEmpty()) { Node curr = q.poll(); int u = curr.getNum(); // 맨 처음 배운 강의에서 넣어줬던 코드 // 이 visited라는 개념이 필요 없는 이유는... // visited를 해줘야 하는 경우가 for문 뺑뺑이인 경우임 // for dist[i][j] 전부 돌리는 경우 /*if(curr.isVisited()) continue; curr.setVisited(true);*/ List < int [] > list = curr.getEdgeList(); for ( int i = 0 ; i < list.size(); i + + ) { int v = list.get(i)[ 0 ]; // 반례 // 1 1 // 1 // 1 2 2 // answer : 0 if (v > NodeList.size() - 1 ) continue ; int dist = list.get(i)[ 1 ]; if (NodeList.get(v).getMinDist() > NodeList.get(u).getMinDist() + dist) { NodeList.get(v).setMinDist(NodeList.get(u).getMinDist() + dist); q.offer(NodeList.get(v)); } } } } public static void main( String [] args) throws IOException{ String [] str = br.readLine(). split ( " " ); int V = Integer. parseInt (str[ 0 ]); int E = Integer. parseInt (str[ 1 ]); int K = Integer. parseInt (br.readLine()); NodeList = new ArrayList < > (); for ( int i = 0 ; i < = V; i + + ) { NodeList. add ( new Node(i)); } for ( int i = 1 ; i < = E; i + + ) { str = br.readLine(). split ( " " ); int u = Integer. parseInt (str[ 0 ]); int v = Integer. parseInt (str[ 1 ]); int w = Integer. parseInt (str[ 2 ]); NodeList.get(u).getEdgeList(). add ( new int [] {v,w}); } dijkstra(K); for ( int i = 1 ; i < NodeList.size(); i + + ) { if (NodeList.get(i).getMinDist() = = INF) System . out . println ( "INF" ); else System . out . println (NodeList.get(i).getMinDist()); } // bw.write(""); // bw.flush(); // bw.close(); } public static class Node{ private List < int [] > edgeList; //[{v1, Dist1}, {v2,Dist2},..] private int num; private boolean visited; // 의미 없는 variable private int minDist; Node( int num) { this .num = num; edgeList = new ArrayList < > (); minDist = INF; visited = false ; } public int getNum() { return num; } public void setNum( int num) { this .num = num; } public List < int [] > getEdgeList() { return edgeList; } public void setEdgeList(List < int [] > edgeList) { this .edgeList = edgeList; } public boolean isVisited() { return visited; } public void setVisited( boolean visited) { this .visited = visited; } public int getMinDist() { return minDist; } public void setMinDist( int minDist) { this .minDist = minDist; } } } Colored by Color Scripter

from http://aig2029.tistory.com/280 by ccl(A) rewrite - 2021-09-17 22:02:07