fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. class CLSHDN{
  4.     static long INF = Long.MAX_VALUE>>2;
  5.  
  6.     static class Edge{
  7.         int fr, to, wt;
  8.         Edge(int a, int b, int c){
  9.             fr = a; to = b; wt = c;
  10.         }
  11.  
  12.         @Override
  13.         public int hashCode(){
  14.             int hc = 31*fr;
  15.             hc = hc*31 + to;
  16.             return hc;
  17.         }
  18.  
  19.         @Override
  20.         public boolean equals(Object o){
  21.             if(o==null || !(o instanceof Edge))
  22.                 return false;
  23.             Edge e = (Edge)o;
  24.             return fr==e.fr && to==e.to;
  25.         }
  26.  
  27.     }
  28.  
  29.     static class Vertex{
  30.         ArrayList<Edge> edges, sptEdges; int ilnd;
  31.         Vertex(){
  32.             edges = new ArrayList<>(); sptEdges = new ArrayList<>(); ilnd = -1;
  33.         }
  34.     }
  35.  
  36.     static class KempeTree{
  37.         long t[];
  38.         int N;
  39.         KempeTree(int n){
  40.             N = (int)Math.pow(2, Math.ceil(Math.log(n)/Math.log(2)));
  41.             t = new long[N+n];
  42.             Arrays.fill(t, INF);
  43.         }
  44.  
  45.         void rangeUpdate(int i, int j, long v){
  46.             for(i+=N, j+=N; i<=j; i=(i+1)/2, j=(j-1)/2){
  47.                 if(i%2==1)
  48.                     t[i] = Math.min(t[i], v);
  49.                 if(j%2==0)
  50.                     t[j] = Math.min(t[j], v);
  51.             }
  52.         }
  53.  
  54.         long query(int i){
  55.             long v = INF;
  56.             for(int j=i+N; j>0; j/=2)
  57.                 v = Math.min(t[j], v);
  58.             return v;
  59.         }
  60.     }
  61.  
  62.     static int n, m, s, t, q;
  63.     static Vertex g[];
  64.     static Edge el[];
  65.     static long ds[], dt[];
  66.     static KempeTree kt;
  67.     static HashSet<Edge> bridges;
  68.     public static void main(String args[])throws Exception{
  69.         Reader re = new Reader(System.in);
  70.         int T = re.nextInt();
  71.         while(T-->0){
  72.             n = re.nextInt();
  73.             m = re.nextInt();
  74.             g = new Vertex[n];
  75.             el = new Edge[m*2];
  76.             for(int i=0; i<n; i++)
  77.                 g[i] = new Vertex();
  78.             for(int i=0; i<m; i++){
  79.                 int u = re.nextInt();
  80.                 int v = re.nextInt();
  81.                 int w = re.nextInt();
  82.                 el[2*i] = new Edge(u, v, w);
  83.                 el[2*i+1] = new Edge(v, u, w);
  84.                 g[u].edges.add(el[2*i]);
  85.                 g[v].edges.add(el[2*i+1]);
  86.             }
  87.             s = re.nextInt();
  88.             t = re.nextInt();
  89.             work();
  90.             q = re.nextInt();
  91.             while(q-->0){
  92.                 int u = re.nextInt();
  93.                 int v = re.nextInt();
  94.                 if(ds[v]<ds[u]){
  95.                     int t = v; v = u; u = t;
  96.                 }
  97.                 if(bridges.contains(new Edge(u, v, 0))){
  98.                     long out = kt.query(g[u].ilnd);
  99.                     System.out.println(out>=INF?"Infinity":out);
  100.                 }
  101.                 else
  102.                     System.out.println(ds[t]);
  103.             }
  104.         }
  105.     }
  106.  
  107.     static void work(){
  108.         // COMPUTE DS AND DT
  109.         Edge prev[] = new Edge[n];
  110.         dt = dijkstra(g, t, s, prev);
  111.         ds = dijkstra(g, s, t, prev);
  112.  
  113.         // FIND ALL BRIDGES
  114.         ArrayList<Edge> opt = new ArrayList<>();
  115.         bridges = new HashSet<>();
  116.         int nb = findBridges(opt);
  117.  
  118.         //IDENTIFY ISLANDS
  119.         identifyIslands(prev);
  120.  
  121.         //GET BYPASS VALUES
  122.         kt = new KempeTree(nb);
  123.         fillBypass();
  124.     }
  125.  
  126.     static int findBridges(ArrayList<Edge> opt){
  127.         for(int i=0; i<el.length; i++){
  128.             Edge e = el[i];
  129.             if(ds[e.fr]+e.wt+dt[e.to]==ds[t]){
  130.                 opt.add(e);
  131.                 el[i] = null;
  132.             }
  133.         }
  134.         Collections.sort(opt, new Comparator<Edge>(){
  135.                 public int compare(Edge e1, Edge e2){
  136.                     if(ds[e1.fr]==ds[e2.fr])
  137.                         return ds[e1.to]==ds[e2.to] ? 0 : ds[e1.to]<ds[e2.to]? -1 : 1;
  138.                     else
  139.                         return ds[e1.fr]<ds[e2.fr] ? -1 : 1;
  140.                 }
  141.             });
  142.         int nb = 0;
  143.         if(opt.size()==1){
  144.             bridges.add(opt.get(0)); nb++;
  145.         }
  146.         else{
  147.             if(ds[opt.get(0).to]<=ds[opt.get(1).fr]){
  148.                 bridges.add(opt.get(0)); nb++;
  149.             }
  150.             Edge e = opt.get(opt.size()-1);
  151.             if(ds[e.fr]>=ds[opt.get(opt.size()-2).to] && !bridges.contains(e)){
  152.                 bridges.add(e); nb++;
  153.             }
  154.             for(int i=1; i<opt.size()-1; i++){
  155.                 e = opt.get(i);
  156.                 if(ds[e.fr]>=ds[opt.get(i-1).to] && ds[e.to]<=ds[opt.get(i+1).fr]){
  157.                     bridges.add(e); nb++;
  158.                 }
  159.             }
  160.         }
  161.         return nb;
  162.     }
  163.  
  164.     static void identifyIslands(Edge prev[]){
  165.         for(Edge e : prev)
  166.             if(e!=null)
  167.                 g[e.fr].sptEdges.add(e);
  168.         class State{
  169.             int v, currIlnd;
  170.             State(int v1, int ci){
  171.                 v = v1; currIlnd = ci;
  172.             }
  173.         }
  174.         Deque<State> stack = new LinkedList<>();
  175.         stack.push(new State(s, 0));
  176.         while(!stack.isEmpty()){
  177.             State st = stack.pop();
  178.             g[st.v].ilnd = st.currIlnd;
  179.             for(Edge e : g[st.v].sptEdges){
  180.                 if(bridges.contains(e))
  181.                     stack.push(new State(e.to, st.currIlnd+1));
  182.                 else
  183.                     stack.push(new State(e.to, st.currIlnd));
  184.             }
  185.         }
  186.     }
  187.  
  188.     static void fillBypass(){
  189.         for(Edge e : el)
  190.             if(e!=null)
  191.                 kt.rangeUpdate(g[e.fr].ilnd, g[e.to].ilnd-1, ds[e.fr]+e.wt+dt[e.to]);
  192.     }
  193.  
  194.     static long[] dijkstra(Vertex g[], int s, int t, Edge prev[]){
  195.         long dist[] = new long[g.length];
  196.         Arrays.fill(dist, INF);
  197.         dist[s] = 0;
  198.         prev[s] = null;
  199.         PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
  200.                     public int compare(Integer u, Integer v){
  201.                         return dist[u]==dist[v] ? 0 : dist[u]<dist[v] ? -1 : 1;
  202.                     }
  203.                 });
  204.         pq.add(s);
  205.  
  206.         while(!pq.isEmpty()){
  207.             int curr = pq.poll();
  208.             if(curr==t)
  209.                 continue;
  210.             if(dist[curr]>=INF)
  211.                 break;
  212.             Vertex v = g[curr];
  213.             for(Edge e : v.edges){
  214.                 if(dist[curr]+e.wt < dist[e.to]){
  215.                     pq.remove(e.to);
  216.                     dist[e.to] = dist[curr]+e.wt;
  217.                     prev[e.to] = e;
  218.                     pq.add(e.to);
  219.                 }
  220.             }
  221.         }
  222.         return dist;
  223.     }
  224. }
  225.  
  226. class Reader{
  227.     BufferedReader br;
  228.     StringTokenizer st;
  229.     Reader(InputStream in) throws Exception{
  230.         br = new BufferedReader(new InputStreamReader(in));
  231.         st = new StringTokenizer("");
  232.     }
  233.  
  234.     String next() throws Exception{
  235.         while(!st.hasMoreTokens())
  236.             st = new StringTokenizer(br.readLine());
  237.         return st.nextToken();
  238.     }
  239.  
  240.     int nextInt() throws Exception{
  241.         return Integer.parseInt(next());
  242.     }
  243.  
  244.     double nextDouble() throws Exception{
  245.         return Double.parseDouble(next());
  246.     }
  247. }
Success #stdin #stdout 0.1s 320576KB
comments (?)
stdin
copy 
1
6 9
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
2 4 5
3 5 8
1 3 3
0 2 4
0 5
9
0 1
1 2
2 3
3 4
4 5
2 4
3 5
1 3
0 2
stdout
copy 
7
6
6
8
11
5
5
5
5
https://ideone.com/74mfM2
language:
Java (HotSpot 12)
created:
8 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!