Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- import java.lang.*;
- public class Main {
- public static class Node {
- int val, w;
- Node(int val, int weight) {
- this.val = val;
- this.w = weight;
- }
- }
- public static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
- {
- // Write your code here
- int[] ans = new int[V];
- Arrays.fill(ans, -1);
- PriorityQueue<Node> pq = new PriorityQueue<>((Node a, Node b) -> a.w - b.w);
- pq.offer(new Node(S, 0));
- while(!pq.isEmpty()) {
- Node temp = pq.poll();
- if (ans[temp.val] != -1) continue;
- ans[temp.val] = temp.w;
- for (List<Integer> next : adj.get(temp.val)) {
- pq.offer(new Node(next.get(0), temp.w + next.get(1)));
- }
- }
- return ans;
- }
- public static void main(String args[]) throws IOException {
- BufferedReader read =
- new BufferedReader(new InputStreamReader(System.in));
- String str[] = read.readLine().trim().split(" ");
- int V = Integer.parseInt(str[0]);
- int E = Integer.parseInt(str[1]);
- ArrayList<ArrayList<ArrayList<Integer>>> adj = new ArrayList<ArrayList<ArrayList<Integer>>>();
- for(int i=0;i<V;i++)
- {
- adj.add(new ArrayList<ArrayList<Integer>>());
- }
- int i=0;
- while (i++<E) {
- String S[] = read.readLine().trim().split(" ");
- int u = Integer.parseInt(S[0]);
- int v = Integer.parseInt(S[1]);
- int w = Integer.parseInt(S[2]);
- ArrayList<Integer> t1 = new ArrayList<Integer>();
- ArrayList<Integer> t2 = new ArrayList<Integer>();
- t1.add(v);
- t1.add(w);
- t2.add(u);
- t2.add(w);
- adj.get(u).add(t1);
- adj.get(v).add(t2);
- }
- int S = Integer.parseInt(read.readLine());
- int[] ptr = dijkstra(V, adj, S);
- for(i=0; i<V; i++)
- System.out.print(ptr[i] + " ");
- System.out.println();
- }
- }
Add Comment
Please, Sign In to add comment