杭电 1874 AC代码 JAVA实现

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{

	static final int infinity=100000;//最终结果与这个值是多少无关。原来定义的double infinity=1.0/0没有意义
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);

		while(in.hasNext()) {
			
			int n=in.nextInt();//原来这些输入都在循环外面，是不对的
			int m=in.nextInt();
			
			int dis[] = new int[n];
			int count[] = new int[n];
			boolean used[] = new boolean[n];
			
			int graph[][] = new int[n][n];
			for(int i=0;i<n;i++) {//原来的话graph数组没有初始化，所以对后来spfa算法里if的判断条件造成了影响
				for(int j=0;j<n;j++) {
//					if(i==j) {
//						graph[i][j] =0;
//					}else {
						graph[i][j] = infinity;
					//}
					
				}
			}
		
		
			for(int i=0;i<m;i++) {//原先写的是i<n
			
				int r=in.nextInt();
				int c=in.nextInt();
				int value = in.nextInt();
				if(value<graph[r][c])//这里总是会出现ArrayIndexOutOfBoundsException
					graph[r][c] = graph[c][r]= value;//原先这里没写对称也相等，因为是双向的路
			}
			int start=in.nextInt();
			int end = in.nextInt();
		
			for(int i=0;i<n;i++) {
				dis[i] = i==start?0:infinity;
			}
			//System.out.println(dis[start]);
		
			spfa(dis,graph,used,count,end,start);
		}
		
		in.close();
	
	}
	

	
	public static void spfa(int dis[],int graph[][],boolean used[],int count[],int end,int start) {
		
		Queue<Integer> q= new LinkedList<Integer>();
		q.add(start);//原先写的是q.add(0),used[0],count[0]，这是我一直WA的原因，还是太马虎了555555555
		used[start] = true;
		count[start]++;
		int tempt=0;
		//boolean flag=true;
		while(!q.isEmpty()) {
			
			//int head = q.peek();//原来q.poll()及Used[head]=false是在这里的，给挪到后面去了
			int head=q.poll();
			used[head] = false;
		
			for(int i=0;i<dis.length;i++) {
				if(i!=head&&graph[head][i]!=infinity&&dis[head]!=infinity) {
						dis[i] = dis[i]>dis[head]+graph[head][i]?dis[head]+graph[head][i]:dis[i];
						
						if(!used[i]) {//原来上面的dis[i]=……是在if条件里面，逻辑好像有些问题
							used[i] = true;
							q.add(i);
							count[i]++;
							tempt=i;
						}
				}
			}
			if(count[tempt]>dis.length) {
				//flag = false;没什么用
				break;
			}
//			q.poll();
//			used[head] = false;
		}

		if(dis[end]!=infinity) {//原来此处写的是if(!flag)
			//System.out.println(100);
			System.out.println(dis[end]);
		}else {
			//System.out.println(200);
			System.out.println(-1);
		}
	}
}