Til the Cows Come Home
描述
贝茜在地里，想在农夫约翰叫醒她准备早上挤奶之前，回到谷仓里尽可能多地睡一觉。贝西需要睡美容觉，所以她想尽快回来。
农夫约翰的田地里有N个地标（2<=N<=1000），唯一编号为1..N。地标1是谷仓；贝茜整天站着的苹果树林是N。
奶牛在田野中行走，在地标之间使用不同长度的T（1<=T<=2000）双向奶牛步道。
贝西对自己的导航能力没有信心，所以一旦启动它，她总是从头到尾保持跟踪。
考虑到路标之间的小路，确定贝西返回谷仓必须走的最小距离。可以保证存在这样的路径。
输入
第1行：两个整数：T和N
行2..T+1：每行用三个空格分隔的整数来描述一个轨迹。前两个整数是轨迹所经过的地标。第三个整数是轨迹的长度，范围为1..100。
输出
第1行：一个整数，贝西从地标N到地标1的最小距离。
Sample Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/**
*
*
*思路：迪杰斯特拉
* @author XA-GDD
*
*/
public class C_TilTheCowsComeHome {
static int T,N;
static ArrayList<ArrayList<int[]>> adjList = new ArrayList<ArrayList<int[]>>();
static int [] minDist;
static boolean [] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
StringTokenizer st;
while((str = br.readLine()) != null) {
if("".equals(str)) break;
st = new StringTokenizer(str);
T = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
adjList.clear();
minDist = new int[N+2];
visited = new boolean[N+2];
for(int i=0;i<=N;i++) {
adjList.add(new ArrayList<int[]>());
}
for(int i=0;i<T;i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
adjList.get(s).add(new int[] {e,dist});
adjList.get(e).add(new int[] {s,dist});
}
dijkstra(N);
System.out.println(minDist[1]);
}
}
static void dijkstra(int start) {
PriorityQueue<int []> pq = new PriorityQueue<int[]>(11,new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
Arrays.fill(minDist, Integer.MAX_VALUE);
pq.add(new int[] {start,0});
minDist[start]=0;
while(!pq.isEmpty()) {
int [] curr = pq.poll();
if(visited[curr[0]]) {
continue;
}
visited[curr[0]]=true;
for(int i=0;i<adjList.get(curr[0]).size();i++) {
int next[] = adjList.get(curr[0]).get(i).clone();
if(minDist[next[0]]>minDist[curr[0]]+next[1]) {
next[1] += minDist[curr[0]];
minDist[next[0]] = minDist[curr[0]]+next[1];
pq.add(new int[] {next[0],minDist[next[0]]});
}
}
}
}
}