NowCoder今年买了一辆新车，他决定自己开车回家过年。回家过程中要经过ň个大小收费站，每个收费站的费用不同，你能帮他计算一下最少需要给多少过路费吗？
输入描述：
输入包含多组数据，每组数据第一行包含两个正整数M（1≤m≤500）和N（1≤n≤30），其中Ñ表示有Ñ个收费站，编号依次为1,2 ，...，n。出发地的编号为0，终点的编号为n，即需要从0到n。 紧接着m行，每行包含三个整数f，t，c，（0≤f，t≤n ; 1≤c≤10），分别表示从编号为˚F的地方开到吨，需要交Ç元的过路费。
输出描述：
对应每组数据，请输出至少需要交多少过路费。
示例1
输入
8 4
0 1 10
0 2 5
1 2 2
1 3 1
2 1 3
2 3 9
2 4 2
3 4 4
输出
7
代码如下：
package com.yzh.hehe; import java.util.ArrayList;
import java.util.List;
import java.util.Scanner; public class LeatestCarFee { public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while (scanner.hasNext()) {
String string=scanner.nextLine();
int m =Integer.valueOf(string.split("\\s+")[0]);
int n =Integer.valueOf(string.split("\\s+")[1]);
List<FeeLine>[] arr = new List[n];
for (int i = 0; i < arr.length; i++) {
arr[i]=new ArrayList<FeeLine>();
}
for (int i = 0; i < m; i++) {
string=scanner.nextLine();
String[] sArr = string.split("\\s+");
makeGraph(arr, sArr);
}
System.out.println(leatestCarFee(arr));
}
scanner.close(); } private static int leatestCarFee(List<FeeLine>[] arr) {
int[] costArr = new int[arr.length+1];//记录起点到各点的最小值
//索引0位置的值设为0（初始值）
for (int i = 1; i < costArr.length; i++) {
costArr[i]=Integer.MAX_VALUE;
}
int[] findArr=new int[arr.length+1];//是否被找到值得点
int aim = 0;
while (aim!=arr.length) {
findArr[aim]=1;
aim=getLeatest(costArr, aim, arr,findArr);
}
return costArr[aim]; } //首先找到离起点值最小（v）的点（m），点m与起点的最小值即为v,再把v与点m的邻接点（n...）的值相加和起点到这些点（n...）的值作比较更新
//重复以上步骤找出所求点到起点的最小值
private static int getLeatest(int[] costArr, int point, List<FeeLine>[] arr,int[] findArr) {
int size=arr[point].size();
int pFee=costArr[point];
for (int i = 0; i < size; i++) {
FeeLine feeLine=arr[point].get(i);
if (feeLine.fee+pFee<costArr[feeLine.point]) {
costArr[feeLine.point]=feeLine.fee+pFee;
}
}
FeeLine rec=new FeeLine(Integer.MAX_VALUE, Integer.MAX_VALUE);
for (int i = 1; i < costArr.length; i++) {
if (costArr[i]<rec.fee&&findArr[i]!=1) {
rec.fee=costArr[i];
rec.point=i;
}
}
return rec.point;
} private static void makeGraph(List<FeeLine>[] arr,String[] sArr ) {
FeeLine feeLine=new FeeLine(Integer.valueOf(sArr[1]), Integer.valueOf(sArr[2]));
arr[Integer.valueOf(sArr[0])].add(feeLine);
} } class FeeLine {
int point;
int fee;
FeeLine(int point,int fee){
this.point=point;
this.fee=fee;
}
}