fork download 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. /**
  5.  * Created by Shreyans on 4/21/2015 at 1:37 AM using IntelliJ IDEA (Fast IO Template)
  6.  */
  7.  
  8. //ADD PUBLIC FOR CF,TC
  9. class EZDIJKST
  10. {
  11.     public static void main(String[] args) throws Exception
  12.     {
  13.         InputReader in = new InputReader(System.in);
  14.         OutputWriter out = new OutputWriter(System.out);
  15.         int t=in.readInt();
  16.         for(int i1=0;i1<t;i1++)
  17.         {
  18.             List<ArrayList<Node>>gr=new ArrayList<ArrayList<Node>>();
  19.             int v=in.readInt(); //Entering Number of Vertices
  20.             for(int i=0;i<=v;i++)
  21.             {
  22.                 gr.add(new ArrayList<Node>());
  23.             }
  24.             int e=in.readInt(); //Entering Number of Edges
  25.             for(int i=0;i<e;i++)//Entering <Vertex> <Adjacent Vertex> <Weight>
  26.             {
  27.                 int a=in.readInt();
  28.                 int b=in.readInt();
  29.                 int c=in.readInt();
  30.                 gr.get(a).add(new Node(b,c));
  31.             }//Built Graph
  32.             int s=in.readInt();//Entering Source
  33.             int des=in.readInt();//Entering Destination
  34.             Queue<Node> pq=new PriorityQueue<Node>(new Node());//Heap to extract value
  35.             Set<Integer>ch=new HashSet<Integer>();//Set to keep track of checked values
  36.             int[]d=new int[v+1];//Keeping track of distances
  37.             Arrays.fill(d,Integer.MAX_VALUE);
  38.             d[s]=0;
  39.             pq.clear();
  40.             pq.add(new Node(s,0));
  41.             while(!pq.isEmpty())
  42.             {
  43.                 Node x=pq.remove();
  44.                 int V=x.node;//Getting next node from heap
  45.                 int W=x.cost;//Getting cost
  46.                 if(V==des)//Shortest Distance to Destinantion Vertex FOUND. If not break, then TLE
  47.                 {
  48.                     break;
  49.                 }
  50.                 ch.add(V);//Adding vertex to checked
  51.                 for(int i=0;i<gr.get(V).size();i++)
  52.                 {
  53.                     Node z=gr.get(V).get(i);
  54.                     if(!ch.contains(z.node))
  55.                     {
  56.                         int v1=z.node;
  57.                         int w1=z.cost;
  58.                         if(d[v1]>W+w1)
  59.                         {
  60.                             d[v1]=W+w1;
  61.                         }
  62.                         pq.add(new Node(v1,d[v1]));
  63.                     }
  64.                 }
  65.             }
  66.             if(d[des]==Integer.MAX_VALUE)
  67.             {
  68.                 out.printLine("NO");
  69.             }
  70.             else
  71.             {
  72.                 out.printLine(d[des]);
  73.             }
  74.         }
  75.         {
  76.             out.close();
  77.         }
  78.     }
  79.  
  80.     //FAST IO
  81.     private static class InputReader
  82.     {
  83.         private InputStream stream;
  84.         private byte[] buf = new byte[1024];
  85.         private int curChar;
  86.         private int numChars;
  87.         private SpaceCharFilter filter;
  88.  
  89.         public InputReader(InputStream stream)
  90.         {
  91.             this.stream = stream;
  92.         }
  93.  
  94.         public int read()
  95.         {
  96.             if (numChars == -1)
  97.                 throw new InputMismatchException();
  98.             if (curChar >= numChars)
  99.             {
  100.                 curChar = 0;
  101.                 try
  102.                 {
  103.                     numChars = stream.read(buf);
  104.                 } catch (IOException e)
  105.                 {
  106.                     throw new InputMismatchException();
  107.                 }
  108.                 if (numChars <= 0)
  109.                     return -1;
  110.             }
  111.             return buf[curChar++];
  112.         }
  113.  
  114.         public int readInt()
  115.         {
  116.             int c = read();
  117.             while (isSpaceChar(c))
  118.                 c = read();
  119.             int sgn = 1;
  120.             if (c == '-')
  121.             {
  122.                 sgn = -1;
  123.                 c = read();
  124.             }
  125.             int res = 0;
  126.             do
  127.             {
  128.                 if (c < '0' || c > '9')
  129.                     throw new InputMismatchException();
  130.                 res *= 10;
  131.                 res += c - '0';
  132.                 c = read();
  133.             } while (!isSpaceChar(c));
  134.             return res * sgn;
  135.         }
  136.  
  137.         public String readString()
  138.         {
  139.             int c = read();
  140.             while (isSpaceChar(c))
  141.                 c = read();
  142.             StringBuilder res = new StringBuilder();
  143.             do
  144.             {
  145.                 res.appendCodePoint(c);
  146.                 c = read();
  147.             } while (!isSpaceChar(c));
  148.             return res.toString();
  149.         }
  150.  
  151.         public double readDouble()
  152.         {
  153.             int c = read();
  154.             while (isSpaceChar(c))
  155.                 c = read();
  156.             int sgn = 1;
  157.             if (c == '-')
  158.             {
  159.                 sgn = -1;
  160.                 c = read();
  161.             }
  162.             double res = 0;
  163.             while (!isSpaceChar(c) && c != '.')
  164.             {
  165.                 if (c == 'e' || c == 'E')
  166.                     return res * Math.pow(10, readInt());
  167.                 if (c < '0' || c > '9')
  168.                     throw new InputMismatchException();
  169.                 res *= 10;
  170.                 res += c - '0';
  171.                 c = read();
  172.             }
  173.             if (c == '.')
  174.             {
  175.                 c = read();
  176.                 double m = 1;
  177.                 while (!isSpaceChar(c))
  178.                 {
  179.                     if (c == 'e' || c == 'E')
  180.                         return res * Math.pow(10, readInt());
  181.                     if (c < '0' || c > '9')
  182.                         throw new InputMismatchException();
  183.                     m /= 10;
  184.                     res += (c - '0') * m;
  185.                     c = read();
  186.                 }
  187.             }
  188.             return res * sgn;
  189.         }
  190.  
  191.         public long readLong()
  192.         {
  193.             int c = read();
  194.             while (isSpaceChar(c))
  195.                 c = read();
  196.             int sgn = 1;
  197.             if (c == '-')
  198.             {
  199.                 sgn = -1;
  200.                 c = read();
  201.             }
  202.             long res = 0;
  203.             do
  204.             {
  205.                 if (c < '0' || c > '9')
  206.                     throw new InputMismatchException();
  207.                 res *= 10;
  208.                 res += c - '0';
  209.                 c = read();
  210.             } while (!isSpaceChar(c));
  211.             return res * sgn;
  212.         }
  213.  
  214.         public boolean isSpaceChar(int c)
  215.         {
  216.             if (filter != null)
  217.                 return filter.isSpaceChar(c);
  218.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  219.         }
  220.  
  221.         public String next()
  222.         {
  223.             return readString();
  224.         }
  225.  
  226.         public interface SpaceCharFilter
  227.         {
  228.             public boolean isSpaceChar(int ch);
  229.         }
  230.     }
  231.  
  232.     private static class OutputWriter
  233.     {
  234.         private final PrintWriter writer;
  235.  
  236.         public OutputWriter(OutputStream outputStream)
  237.         {
  238.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  239.         }
  240.  
  241.         public OutputWriter(Writer writer)
  242.         {
  243.             this.writer = new PrintWriter(writer);
  244.         }
  245.  
  246.         public void print(Object... objects)
  247.         {
  248.             for (int i = 0; i < objects.length; i++)
  249.             {
  250.                 if (i != 0)
  251.                     writer.print(' ');
  252.                 writer.print(objects[i]);
  253.             }
  254.         }
  255.  
  256.         public void printLine(Object... objects)
  257.         {
  258.             print(objects);
  259.             writer.println();
  260.         }
  261.  
  262.         public void close()
  263.         {
  264.             writer.close();
  265.         }
  266.  
  267.         public void flush()
  268.         {
  269.             writer.flush();
  270.         }
  271.     }
  272. }
  273.  
  274. class Node implements Comparator<Node>
  275. {
  276.     public int node;
  277.     public int cost;
  278.  
  279.     public Node()
  280.     {
  281.  
  282.     }
  283.     public Node(int node, int cost)
  284.     {
  285.         this.node = node;
  286.         this.cost = cost;
  287.     }
  288.  
  289.     @Override
  290.     public int compare(Node node1, Node node2)
  291.     {
  292.         if (node1.cost < node2.cost)
  293.             return -1;
  294.         if (node1.cost > node2.cost)
  295.             return 1;
  296.         return 0;
  297.     }
  298. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin 
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3
stdout 
12
5
NO
https://ideone.com/p7u5vN
language:
Java (HotSpot 12)
created:
10 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!