fork(1) download
copy 
  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<AbstractMap.SimpleEntry<Integer,Integer>>> gr=new ArrayList<ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>>();//AbstractMap.SimpleEntry<Integer,Integer> is similar to pair<int a,int b> in C++
  19.             int v=in.readInt();
  20.             int e=in.readInt();
  21.             Set<Integer> vertices=new HashSet<Integer>();
  22.             for(int i=0;i<=v;i++)
  23.             {
  24.                 vertices.add(i);
  25.                 gr.add(new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>());
  26.             }
  27.             vertices.remove(0);//Not intended hence removed
  28.             for(int i=0;i<e;i++)
  29.             {
  30.                 int a = in.readInt();
  31.                 int b = in.readInt();
  32.                 int c = in.readInt();
  33.                 gr.get(a).add(new AbstractMap.SimpleEntry<Integer, Integer>(b, c));
  34.             }
  35.             int s=in.readInt();
  36.             int des=in.readInt();
  37.             Comparator<AbstractMap.SimpleEntry<Integer, Integer>> comparator=new WeightComparator();
  38.             TreeSet<AbstractMap.SimpleEntry<Integer, Integer>>ts=new TreeSet<AbstractMap.SimpleEntry<Integer, Integer>>(comparator);
  39.             int[]d=new int[v+1];
  40.             Arrays.fill(d,Integer.MAX_VALUE);
  41.             d[s]=0;
  42.             vertices.remove(s);
  43.             for(AbstractMap.SimpleEntry<Integer, Integer> pair:gr.get(s))
  44.             {
  45.                 ts.add(pair);
  46.                 d[pair.getKey()]=pair.getValue();
  47.             }
  48.             while(!vertices.isEmpty()&&!ts.isEmpty())
  49.             {
  50.                 AbstractMap.SimpleEntry<Integer, Integer> curr=ts.pollFirst();
  51.                 int V=curr.getKey();
  52.                 int W=curr.getValue();
  53.                 for(AbstractMap.SimpleEntry<Integer, Integer> pair:gr.get(V))
  54.                 {
  55.                     int v1=pair.getKey();
  56.                     int w1=pair.getValue();
  57.                     if(d[v1]>W+w1)
  58.                     {
  59.                         d[v1]=W+w1;
  60.                     }
  61.                     ts.add(pair);
  62.                 }
  63.                 vertices.remove(V);
  64.             }
  65.             if(d[des]==Integer.MAX_VALUE)
  66.             {
  67.                 out.printLine("NO");
  68.             }
  69.             else
  70.             {
  71.                 out.printLine(d[des]);
  72.             }
  73.         }
  74.         Map.Entry<Integer, Integer> pair=new AbstractMap.SimpleEntry<Integer,Integer>(1,1);
  75.         {
  76.             out.close();
  77.         }
  78.     }
  79.     static public class WeightComparator implements
  80.             Comparator<AbstractMap.SimpleEntry<Integer, Integer>>
  81.     {
  82.         @Override
  83.         public int compare(AbstractMap.SimpleEntry<Integer, Integer> one,
  84.                            AbstractMap.SimpleEntry<Integer, Integer> two)
  85.         {
  86.             return Integer.compare(one.getValue(), two.getValue());
  87.         }
  88.     }
  89.  
  90.     //FAST IO
  91.     private static class InputReader
  92.     {
  93.         private InputStream stream;
  94.         private byte[] buf = new byte[1024];
  95.         private int curChar;
  96.         private int numChars;
  97.         private SpaceCharFilter filter;
  98.  
  99.         public InputReader(InputStream stream)
  100.         {
  101.             this.stream = stream;
  102.         }
  103.  
  104.         public int read()
  105.         {
  106.             if (numChars == -1)
  107.                 throw new InputMismatchException();
  108.             if (curChar >= numChars)
  109.             {
  110.                 curChar = 0;
  111.                 try
  112.                 {
  113.                     numChars = stream.read(buf);
  114.                 } catch (IOException e)
  115.                 {
  116.                     throw new InputMismatchException();
  117.                 }
  118.                 if (numChars <= 0)
  119.                     return -1;
  120.             }
  121.             return buf[curChar++];
  122.         }
  123.  
  124.         public int readInt()
  125.         {
  126.             int c = read();
  127.             while (isSpaceChar(c))
  128.                 c = read();
  129.             int sgn = 1;
  130.             if (c == '-')
  131.             {
  132.                 sgn = -1;
  133.                 c = read();
  134.             }
  135.             int res = 0;
  136.             do
  137.             {
  138.                 if (c < '0' || c > '9')
  139.                     throw new InputMismatchException();
  140.                 res *= 10;
  141.                 res += c - '0';
  142.                 c = read();
  143.             } while (!isSpaceChar(c));
  144.             return res * sgn;
  145.         }
  146.  
  147.         public String readString()
  148.         {
  149.             int c = read();
  150.             while (isSpaceChar(c))
  151.                 c = read();
  152.             StringBuilder res = new StringBuilder();
  153.             do
  154.             {
  155.                 res.appendCodePoint(c);
  156.                 c = read();
  157.             } while (!isSpaceChar(c));
  158.             return res.toString();
  159.         }
  160.  
  161.         public double readDouble()
  162.         {
  163.             int c = read();
  164.             while (isSpaceChar(c))
  165.                 c = read();
  166.             int sgn = 1;
  167.             if (c == '-')
  168.             {
  169.                 sgn = -1;
  170.                 c = read();
  171.             }
  172.             double res = 0;
  173.             while (!isSpaceChar(c) && c != '.')
  174.             {
  175.                 if (c == 'e' || c == 'E')
  176.                     return res * Math.pow(10, readInt());
  177.                 if (c < '0' || c > '9')
  178.                     throw new InputMismatchException();
  179.                 res *= 10;
  180.                 res += c - '0';
  181.                 c = read();
  182.             }
  183.             if (c == '.')
  184.             {
  185.                 c = read();
  186.                 double m = 1;
  187.                 while (!isSpaceChar(c))
  188.                 {
  189.                     if (c == 'e' || c == 'E')
  190.                         return res * Math.pow(10, readInt());
  191.                     if (c < '0' || c > '9')
  192.                         throw new InputMismatchException();
  193.                     m /= 10;
  194.                     res += (c - '0') * m;
  195.                     c = read();
  196.                 }
  197.             }
  198.             return res * sgn;
  199.         }
  200.  
  201.         public long readLong()
  202.         {
  203.             int c = read();
  204.             while (isSpaceChar(c))
  205.                 c = read();
  206.             int sgn = 1;
  207.             if (c == '-')
  208.             {
  209.                 sgn = -1;
  210.                 c = read();
  211.             }
  212.             long res = 0;
  213.             do
  214.             {
  215.                 if (c < '0' || c > '9')
  216.                     throw new InputMismatchException();
  217.                 res *= 10;
  218.                 res += c - '0';
  219.                 c = read();
  220.             } while (!isSpaceChar(c));
  221.             return res * sgn;
  222.         }
  223.  
  224.         public boolean isSpaceChar(int c)
  225.         {
  226.             if (filter != null)
  227.                 return filter.isSpaceChar(c);
  228.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  229.         }
  230.  
  231.         public String next()
  232.         {
  233.             return readString();
  234.         }
  235.  
  236.         public interface SpaceCharFilter
  237.         {
  238.             public boolean isSpaceChar(int ch);
  239.         }
  240.     }
  241.  
  242.     private static class OutputWriter
  243.     {
  244.         private final PrintWriter writer;
  245.  
  246.         public OutputWriter(OutputStream outputStream)
  247.         {
  248.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  249.         }
  250.  
  251.         public OutputWriter(Writer writer)
  252.         {
  253.             this.writer = new PrintWriter(writer);
  254.         }
  255.  
  256.         public void print(Object... objects)
  257.         {
  258.             for (int i = 0; i < objects.length; i++)
  259.             {
  260.                 if (i != 0)
  261.                     writer.print(' ');
  262.                 writer.print(objects[i]);
  263.             }
  264.         }
  265.  
  266.         public void printLine(Object... objects)
  267.         {
  268.             print(objects);
  269.             writer.println();
  270.         }
  271.  
  272.         public void close()
  273.         {
  274.             writer.close();
  275.         }
  276.  
  277.         public void flush()
  278.         {
  279.             writer.flush();
  280.         }
  281.     }
  282. }
Success #stdin #stdout 0.11s 320256KB
comments (?)
stdin
copy 
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
copy 
12
5
NO
https://ideone.com/wAQfBu
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

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!