2013
11-11

# Til the Cows Come Home

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John’s field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.

* Line 1: Two integers: T and N

* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

90

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int c=0;
int t=in.nextInt();//输入顺序错误WA了N次！！！看清题意！
int n=in.nextInt();
int dist[]=new int[n+1];//先输入再确定数组大小！！！RE了N次！
int[][] w=new int[n+1][n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
w[i][j]=Integer.MAX_VALUE;
}
}
for(int i=0;i< t;i++){//输入两点及之间距离
int sn=in.nextInt();
int en=in.nextInt();
c=in.nextInt();
if(c< w[sn][en])
w[sn][en]=w[en][sn]=c;
}
dijkstra(n,w,dist);
System.out.println(dist[1]);
}

public static void dijkstra(int v ,int[][] a, int[] dist){//最短路径dijkstra算法
int nn = dist.length - 1 ;
boolean[] s = new boolean[nn+1];
//初始化
for(int i = 1; i <= nn; i++)
dist[i] = a[v][i];
dist[v] = 0;
s[v] = true;
for(int i = 1; i < nn; i++){
int temp =Integer.MAX_VALUE;
int u = v;
for(int j = 1; j < nn; j++){
if(!s[j] && dist[j] < temp&&dist[j]>0){
u = j;
temp = dist[j];
}
}
s[u] = true;  //找到了第一个并入S的节点
for(int j = 1; j <= nn; j++)
if(!s[j] &&dist[u]+a[u][j]< dist[j]&& a[u][j] < Integer.MAX_VALUE)
dist[j] =dist[u]+a[u][j];
}
}
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。