题目描述

Dijkstra堆优化

用的节点的方法，但不知道为啥用了4秒，很迷。。。

java代码

import java.io.;
import java.util.;

class Main{
static final int N = 100010;
static Node[] nodes = new Node[N];
static int n,m;

public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] s1 = br.readLine().split(" ");
    n = Integer.parseInt(s1[0]);
    m = Integer.parseInt(s1[1]);
    for(int i = 1;i<=n;i++){
        nodes[i] = new Node(i);
    }

    while(m--!=0){
        String[] s2 = br.readLine().split(" ");
        int x = Integer.parseInt(s2[0]),y = Integer.parseInt(s2[1]),z = Integer.parseInt(s2[2]);
        add(x,y,z);
    }
    System.out.print(dijkstra());
}

static void add(int a,int b,int c){
    nodes[a].neighbors.add(nodes[b]);
    //nodes[b].wis[a] = Math.min(nodes[b].wis[a],c);
    if(nodes[b].map.get(a)!=null){
        nodes[b].map.put(a,Math.min(nodes[b].map.get(a),c));
    }else{
        nodes[b].map.put(a,c);
    }
}

static int dijkstra(){
    PriorityQueue<Node> pq = new PriorityQueue(new Comparator<Node>() {
        public int compare(Node o1, Node o2) {
            return o1.dist - o2.dist;
        }
    });
    nodes[1].dist = 0;
    pq.add(nodes[1]);
    while(!pq.isEmpty()){
        Node t = pq.poll();
        if(t.val == n){
            break;
        }
        t.st = true;
        for(Node node: t.neighbors){
            if(!node.st){
                node.dist = Math.min(node.dist,t.dist+node.map.get(t.val));
                pq.add(node);
            }
        }
    }
    if(nodes[n].dist==0x3f3f3f3f){
        return -1;
    }else{
        return nodes[n].dist;
    }
}

}

class Node{
int val;
int dist;
boolean st;
Map[HTML_REMOVED] map;
List[HTML_REMOVED] neighbors;

public Node(int a){
    this.val = a;
    this.dist = 0x3f3f3f3f;
    this.st =false;
    this.map = new HashMap();
    this.neighbors = new ArrayList();
}

}
```