packagecsp;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Iterator;importjava.util.LinkedList;importjava.util.List;importjava.util.Scanner;public classMain_201712_4 {private static intn;private final static int MAX =Integer.MAX_VALUE;private static boolean[] finalVex;private static double[] shortPath;private static List>list;public static voidmain(String[] args) {//准备工作

Scanner in = newScanner(System.in);

n=in.nextInt();int nums =in.nextInt();

list= new ArrayList<>();for(int i=0; i

list.add(new LinkedList());

}for(int i=0; i

list.get(start-1).add(new Edge(type, start-1, end-1, weight));

list.get(end-1).add(new Edge(type, end-1, start-1, weight));

}//核心代码

shortPathDij();if(n == 1) {

System.out.println(0);

}else{

System.out.println((long)shortPath[n-1]);

}//关闭流

in.close();

}public static voidshortPathDij() {

Edge tmp= null;

shortPath= new double[n];int[] tails = new int[n];int[] exp = new int[n];

finalVex= new boolean[n];

Arrays.fill(shortPath, MAX);

Arrays.fill(finalVex,false);

Arrays.fill(exp,0);

shortPath[0] = 0;

tails[0] = 1;while(!finalVex[n-1]) {int index =min(shortPath);if(index == -1)break;

LinkedList p = list.get(index);//获得从index位置出发的所有边

Iterator it = p.iterator();//上述边的迭代器

int j=0;while(it.hasNext()) {//遍历这些边

tmp = it.next();//拿到一条边

j = tmp.end;//j为这条边的终点

if(finalVex[j])continue;if(tmp.type==1) {//如果边是小路

int eee = exp[index]+tmp.weight;double sum = shortPath[index]-(int)Math.pow(exp[index], 2)+(int)Math.pow(eee, 2);if(sum

shortPath[j]=sum;

tails[j]= index+1;

exp[j]=eee;

}

}else {//如果边是大路

if((shortPath[index]+tmp.weight)

shortPath[j]= shortPath[index]+tmp.weight;

tails[j]= index+1;

exp[j]= 0;

}

}

}

}

}private static int min(double[] shortPath2) {int index = -1;for(int i=0; i

index=i;if(index==-1)return -1;for(int i=0; ishortPath2[i]&&!finalVex[i])

index=i;

finalVex[index]= true;returnindex;

}

}classEdge{public inttype;public intstart;public intend;public intweight;public Edge(int type, int start, int end, intweight) {this.type =type;this.start =start;this.end =end;this.weight =weight;

}

}