一开始一直卡在11/12,优化了好多次终于过了。。
import java.util.*;
import java.io.*;
class Main {
static final int INF = Integer.MAX_VALUE/2;
//稀疏图,邻接表存储
static int idx,n,m;
static int[] h = new int[200010];
static int[] e = new int[300010];
static int[] ne = new int[300010];
static int[] ve = new int[300010];
//从起点到其他点距离
static int[] dist = new int[200010];
//是否已确定
static boolean[] flag = new boolean[200010];
static {
Arrays.fill(h,-1);
Arrays.fill(dist,INF);
}
//手写堆
static int size;
static int[] heap = new int[200010];
//用于定位结点编号所在堆中的位置
static int[] hl = new int[200010];
//标记结点是否已加入堆中,已加入则修改
static boolean[] inHeap = new boolean[200010];
//加入新边,不处理重边
static void insert(int a, int b, int v) {
/*for (int i = h[a]; i != -1; i=ne[i]) {
if (e[i] == b) {
//新边更短,更新
if (ve[i]>v) ve[i] = v;
return;
}
}*/
e[idx] = b;
ve[idx] = v;
ne[idx] = h[a];
h[a] = idx++;
}
//取出堆顶元素(当前从起点距离最近且未确认的点)
static int getNext() {
if (size == 1) return heap[size--];
int next = heap[1];
heap[1] = heap[size--];
down(1);
return next;
}
//加入堆
static void heapAdd(int x) {
heap[++size] = x;
inHeap[x] = true;
hl[x] = size;
up(size);
}
//修改堆
static void modify(int x) {
int i=hl[x];
up(i);
//down(i);
}
static void swap(int a, int b) {
hl[heap[a]] = b;
hl[heap[b]] = a;
int temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
static void up(int x) {
while (dist[heap[x]]<dist[heap[x/2]] && x>1) {
swap(x,x/2);
x = x/2;
}
}
static void down(int x) {
int t = x;
if (2*x<=size && dist[heap[2*x]]<dist[heap[t]]) t = 2*x;
if ((2*x+1)<=size && dist[heap[2*x+1]]<dist[heap[t]]) t = 2*x+1;
if (t!=x) {
swap(x,t);
down(t);
}
}
static void generateDistance(int start) {
dist[start] = 0;
heapAdd(start);
//堆优化,堆中为空则表示能抵达的最短路已全部构建完成
while (size !=0) {
int next = getNext();
if (flag[next]) continue;
flag[next] = true;
//只需遍历next结点的相邻结点即可
for (int j = h[next]; j!=-1; j=ne[j]) {
int dt = ve[j];
int x = e[j];
if (!flag[x] && dist[x]>dist[next]+dt) {
dist[x] = dist[next]+dt;
if (!inHeap[x]) heapAdd(x);
else modify(x);
}
}
}
}
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String[] strs = in.readLine().split(" ");
n = Integer.parseInt(strs[0]);
m = Integer.parseInt(strs[1]);
for (int i = 0; i < m; i++) {
strs = in.readLine().split(" ");
int a = Integer.parseInt(strs[0]);
int b = Integer.parseInt(strs[1]);
int v = Integer.parseInt(strs[2]);
insert(a,b,v);
}
generateDistance(1);
if (dist[n] == INF) dist[n] = -1;
System.out.println(dist[n]);
in.close();
isr.close();
}
}