fork download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.util.ArrayList;
  5. import java.util.Comparator;
  6. import java.util.HashMap;
  7. import java.util.LinkedList;
  8. import java.util.Map;
  9. import java.util.PriorityQueue;
  10.  
  11. public class Main {
  12.     static class Reader {
  13.  
  14.     final private int BUFFER_SIZE = 1 << 16;
  15.  
  16.     private DataInputStream din;
  17.  
  18.     private byte[] buffer;
  19.  
  20.     private int bufferPointer, bytesRead;
  21.  
  22.     public Reader() {
  23.  
  24.         din = new DataInputStream(System.in);
  25.  
  26.         buffer = new byte[BUFFER_SIZE];
  27.  
  28.         bufferPointer = bytesRead = 0;
  29.  
  30.     }
  31.  
  32.     public Reader(String file_name) throws IOException {
  33.  
  34.         din = new DataInputStream(new FileInputStream(file_name));
  35.  
  36.         buffer = new byte[BUFFER_SIZE];
  37.  
  38.         bufferPointer = bytesRead = 0;
  39.  
  40.     }
  41.  
  42.     public String readLine() throws IOException {
  43.  
  44.         byte[] buf = new byte[64]; // line length
  45.  
  46.         int cnt = 0, c;
  47.  
  48.         while ((c = read()) != -1) {
  49.  
  50.             if (c == '\n') {
  51.  
  52.                 break;
  53.  
  54.             }
  55.  
  56.             buf[cnt++] = (byte) c;
  57.  
  58.         }
  59.  
  60.         return new String(buf, 0, cnt);
  61.  
  62.     }
  63.  
  64.     public int nextInt() throws IOException {
  65.  
  66.         int ret = 0;
  67.  
  68.         byte c = read();
  69.  
  70.         while (c <= ' ') {
  71.  
  72.             c = read();
  73.  
  74.         }
  75.  
  76.         boolean neg = (c == '-');
  77.  
  78.         if (neg) {
  79.  
  80.             c = read();
  81.  
  82.         }
  83.  
  84.         do {
  85.  
  86.             ret = ret * 10 + c - '0';
  87.  
  88.         } while ((c = read()) >= '0' && c <= '9');
  89.  
  90.         if (neg) {
  91.  
  92.             return -ret;
  93.  
  94.         }
  95.  
  96.         return ret;
  97.  
  98.     }
  99.  
  100.     private void fillBuffer() throws IOException {
  101.  
  102.         bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  103.  
  104.         if (bytesRead == -1) {
  105.  
  106.             buffer[0] = -1;
  107.  
  108.         }
  109.  
  110.     }
  111.  
  112.     private byte read() throws IOException {
  113.  
  114.         if (bufferPointer == bytesRead) {
  115.  
  116.             fillBuffer();
  117.  
  118.         }
  119.  
  120.         return buffer[bufferPointer++];
  121.  
  122.     }
  123.  
  124.     public void close() throws IOException {
  125.  
  126.         if (din == null) {
  127.  
  128.             return;
  129.  
  130.         }
  131.  
  132.         din.close();
  133.  
  134.     }
  135.  
  136. }
  137.  
  138. public static void main(String[] args) {
  139.  
  140.     StringBuilder sba = new StringBuilder();
  141.  
  142.     try {
  143.  
  144.         Reader sc = new Reader();
  145.         int t = sc.nextInt();
  146.         while (t-- > 0) {
  147.  
  148.             int n = sc.nextInt();
  149.  
  150.             int numOfEdges = sc.nextInt();
  151.  
  152.             int src = sc.nextInt();
  153.             int dest = sc.nextInt();
  154.  
  155.             //System.out.println("n= "+n+" ,exitcell= "+exitCell+" ,timelimit= "+timeLimit+" and numedges= "+numOfEdges);
  156.             graph g = new graph(src - 1, dest - 1);
  157.  
  158.             for (int i = 0; i < n; i++) {
  159.  
  160.                 g.addVertex(new vertex(i + 1));
  161.  
  162.             }
  163.  
  164.             // System.out.println("going to add edges");
  165.             for (int i = 0; i < numOfEdges; i++) {
  166.                 int source = sc.nextInt();
  167.  
  168.                 int destination = sc.nextInt();
  169.  
  170.                 int weight = sc.nextInt();
  171.                 // System.out.println("num of vertices: "+g.vertexList.size());
  172.  
  173.                 g.addEdge(g.vertexList.get(source - 1), g.vertexList.get(destination - 1), weight);
  174.  
  175.                 // System.out.println("i= "+i);
  176.             }
  177.             // System.out.println("calling disjktra ");
  178.             int count = g.primAlgo(g.vertexList.get(g.srcCellVertexIndex),g.vertexList.get(g.destCellVertexIndex));
  179.             if (count != Integer.MAX_VALUE) {
  180.                 sba.append(count).append("\n");
  181. //                    System.out.println(count);
  182.                 } else {
  183.                     sba.append("NONE").append("\n");
  184. //                    System.out.println("NONE");
  185.                 }
  186.             }
  187. //            sba.deleteCharAt(sba.length()-1);
  188.             System.out.println(sba.toString());
  189.         } catch (Exception e) {
  190.  
  191.         System.out.println(e.getMessage());
  192.  
  193.     }
  194.  
  195. }
  196. }
  197.  
  198. class graph // it is a directed and weighted graph
  199. {
  200.  
  201. public int srcCellVertexIndex, destCellVertexIndex;
  202. ;
  203.  
  204. public ArrayList<vertex> vertexList;
  205.  
  206. public int numOfVertices;
  207.  
  208. public ArrayList<LinkedList<edge>> adjList;
  209.  
  210. public graph(int src, int dest) {
  211.  
  212.     srcCellVertexIndex = src;
  213.     destCellVertexIndex = dest;
  214.  
  215.     vertexList = new ArrayList<>();
  216.  
  217.     adjList = new ArrayList<>();
  218.  
  219.     numOfVertices = 0;
  220.  
  221. }
  222.  
  223. public void addVertex(vertex vert) {
  224.  
  225.     vertexList.add(vert);
  226.  
  227.     adjList.add(new LinkedList<>());
  228.  
  229.     numOfVertices++;
  230.  
  231. }
  232.  
  233. public void addEdge(vertex source, vertex destination, int weight) {
  234.  
  235.  
  236.  
  237.     edge lp = new edge(source, destination, weight);
  238.  
  239.     adjList.get(source.label-1).add(lp);
  240.  
  241.  
  242.  
  243.     lp = new edge(destination, source, weight);
  244.  
  245.     adjList.get(destination.label-1).add(lp);
  246.  
  247.  
  248. }
  249.  
  250. public int primAlgo(vertex entryCell,vertex exitCell) {
  251.     // System.out.println("src cell "+v.label);
  252.     // System.out.println("dest cell "+exitCell.label);
  253.  
  254.  
  255.     PriorityQueue<vertex> pq = new PriorityQueue<>(new Comparator<vertex>() {
  256.  
  257.         @Override
  258.  
  259.         public int compare(vertex t, vertex t1) {
  260.  
  261.             return t.key - t1.key; 
  262.  
  263.         }
  264.  
  265.     });
  266.  
  267.     int count=0;
  268.     entryCell.key=0;
  269.     entryCell.visited=true;
  270.     for(int i=0;i<vertexList.size();i++)
  271.     	pq.offer(vertexList.get(i));
  272.     while(count<vertexList.size()) {
  273.     	vertex curr=pq.poll();
  274. //    	System.out.println("visited "+curr.label+" , ");
  275.     	count+=1;
  276.     	curr.visited=true;
  277.     	adjList.get(curr.label - 1).forEach(e -> {
  278.             if(e.destination!=e.source && !e.destination.visited )
  279. //                {
  280.         			if(e.destination.key>(e.source.key+e.weight))
  281.         				{
  282.             				pq.remove(e.destination);
  283.         					e.destination.key=e.source.key+e.weight;
  284. //                    		System.out.println(e.destination.label+" new key is "+e.destination.key);
  285.                     		pq.add(e.destination);
  286.         				}
  287. //                }
  288.         });
  289.     }
  290.     // System.out.println("returning "+exitCell.timeExhausted);
  291.     return exitCell.key;
  292.  
  293. }
  294. }
  295.  
  296. class vertex {
  297.  
  298. public int label;
  299. public int key;
  300.  
  301. public boolean visited;
  302.  
  303. public vertex(int label) {
  304.  
  305.     this.label = label;
  306.  
  307.     this.visited = false;
  308.  
  309.     this.key = Integer.MAX_VALUE;
  310.  
  311. }
  312. }
  313.  
  314. class edge {
  315.  
  316. vertex source, destination;
  317.  
  318. int weight;
  319.  
  320. public edge(vertex source, vertex destination, int weight) {
  321.  
  322.     this.source = source;
  323.  
  324.     this.destination = destination;
  325.  
  326.     this.weight = weight;
  327.  
  328. }
  329. }
Success #stdin #stdout 0.16s 2184192KB
comments (?)
stdin
copy 
2
4 2 1 4
1 2 5
3 4 5
4 4 1 4
1 2 5
2 3 5
3 4 5
4 2 6
stdout
copy 
NONE
11
https://ideone.com/bzgETX
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!