Til the Cows Come Home

POJ-2387

这题是最简单的最短路求解题，主要就是使用dijkstra算法，时间复杂度是\(O(n^2)\).
需要注意的是，一定要看清楚题目的输入要求，是先输入边，再输入顶点，一开始我没看清，wrong answer了一次。

package POJ;

import java.util.*;

public class POJ_2387 {

	private static int n,t;

	static int [][]w;

	static boolean []flag;//是否被遍历过

	static int sta;//开始结点

	static int []dis;//distance数组

	static final int INF=0x3f3f3f3f;

	public static int dijikstra() {

		dis=new int[n];

		flag=new boolean[n];

		Arrays.fill(flag, false);

		for(int i=0;i<n;i++) {

			if(i!=sta)

				dis[i]=INF;

			else dis[i]=0;

		}

		for(int i=0;i<n;i++) {

			int index=-1,mins=INF;

			for(int j=0;j<n;j++) {

				if(!flag[j]&&dis[j]<=mins) {

					mins=dis[index=j];

				}

			}

			if(index==-1)

				break;

			flag[index]=true;

			for(int j=0;j<n;j++)

				dis[j]=Math.min(dis[j], dis[index]+w[index][j]);

		}

		return dis[0];

	}

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Scanner cin=new Scanner(System.in);

		//注意：这里先输入边再输入顶点！

		t=cin.nextInt();

		n=cin.nextInt();

		w=new int[n][n];

		for(int i=0;i<n;i++){

			for(int j=0;j<n;j++)

				w[i][j]=INF;

			w[i][i]=0;

		}

		for(int i=0;i<t;i++) {

			int from,to;

			from=cin.nextInt();

			to=cin.nextInt();

			int len=cin.nextInt();

			w[from-1][to-1]=w[to-1][from-1]=Math.min(len, w[from-1][to-1]);

		}

		sta=n-1;

		System.out.println(dijikstra());

	}

}

巴特西

POJ-2387(原始dijkstra求最短路)

Til the Cows Come Home

POJ-2387

最新文章

热门文章