Poj Solution 3159

http://poj.org/problem?id=3159

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

class node implements Comparable{
    int v,next,disten;
    node(){
        v = next = disten = -1;
    }
    node(int v,int next,int disten){
        this.v = v;
        this.next = next;
        this.disten = disten;
    }
    void set_node(int v,int next,int disten){
        this.v = v;
        this.next = next;
        this.disten = disten;
    }
    void copy(node obj){
        this.v = obj.v;
        this.next = obj.next;
        this.disten = obj.disten;
    }
    public int compareTo(Object obj){
        
        node cnt = (node)obj;
        if(cnt.disten< disten) return 1;
        return -1;
    }
}
class binary_Heap{
    node tree[];
    int n,p,c;
    binary_Heap(){};
    binary_Heap(int cap){
        n = 0;
        tree = new node[40000];
        for(int i=0;i< 40000;++i) tree[i] = new node();
    }
    void push(node temp){
        for(p=++n;p>1 && tree[p>>1].compareTo(temp)>0;p>>=1){
            tree[p].copy(tree[p>>1]);
        }
        tree[p].copy(temp);

    }
    node front(){return tree[1];}
    void pop(){
        for(p=1,c=2;c< n && tree[c+=(c< n-1 && tree[c+1].compareTo(tree[c])>0)?1:0].
                  compareTo(tree[n])>0;tree[p].copy(tree[c]),p=c,c<<=1);
        
        tree[p].copy(tree[n--]);
    }
}
class Graph{
    int n,top;
    node Map[];
    Graph(){}
    Graph(int n){
        top = n+1;
        this.n = n;
        Map = new node[200000];
        for(int i=0;i< 200000;++i){
            Map[i] = new node();
        }
    }
    void add_edge(int u,int v,int disten){
        Map[top].set_node(v, Map[u].next,disten);
        Map[u].next = top;
        ++top;
    }
    

int get_Dijkstra(int s,int t){
 node temp = new node();
 int BIG = 1000000000;
 int meat[] = new int[n+10];
 //binary_Heap heap = new binary_Heap(n);
 Queue que = new PriorityQueue< node>();
        
 Arrays.fill(meat, BIG);
        
 meat[s] = 0;
 for(int i=Map[s].next;i>=0;i=Map[i].next){
    meat[Map[i].v] = Map[i].disten;
            
    //heap.push(Map[i]);
    que.add(Map[i]);
  }
  //while(heap.n>0){
  while(!que.isEmpty()){
    //temp.copy(heap.front());
    temp.copy((node)que.element());
    que.remove();
    //    heap.pop();

    if(meat[temp.v]==temp.disten){
        for(int i=Map[temp.v].next;i>=0;i=Map[i].next){
            if(meat[Map[i].v]>temp.disten+Map[i].disten){
                meat[Map[i].v] = temp.disten+Map[i].disten;
        //heap.push(new node(Map[i].v,-1,meat[Map[i].v]));
                que.add(new node(Map[i].v,-1,meat[Map[i].v]));
            }
        }
    }
  }
        
    return meat[t];
 }
}

public class Main {
    
 static public void main(String[]args)throws Exception{
        
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
 int n,m,u,v,disten;
 Graph obj;

 n = Get_Num(cin);
 m = Get_Num(cin);
        
 obj = new Graph(n);

  for(int i=0;i< m;++i){
    u = Get_Num(cin);
    v = Get_Num(cin);
    disten = Get_Num(cin);
    obj.add_edge(u, v, disten);
  }
        
    System.out.println(obj.get_Dijkstra(1,n));
 }
    
    static int Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *