微软2016校园招聘在线笔试: [Islands Travel]

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3, Y3) …, (XN, YN). You starts at the 1st island (X1, Y1) and your destination is the n-th island (XN, YN). Travelling between i-th and j-th islands will cost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b} denotes the smaller value between a and b) gold coins. You want to know what is the minimum cost to travel from the 1st island to the n-th island.

输入

Line 1: an integer N.

Line 2~N+1: each line contains two integers Xiand Yi.

For 40% data, N<=1000，0<=Xi,Yi<=100000.

For 100% data, N<=100000，0<=Xi,Yi<=1000000000.

输出

Output the minimum cost.

样例输入32 21 77 6样例输出2import java.io.File;import java.io.FileNotFoundException;import java.util.Scanner;public class Main {final static int MAXINT = 1000000000;public static void main(String[] args) throws FileNotFoundException {Scanner cin = new Scanner(System.in);//Scanner cin = new Scanner(new File("/Users/angelo/Downloads/cordinates.txt"));int count = cin.nextInt();int[][] cord = new int[count][2];for (int i = 0; i < count; i++) {cord[i][0] = cin.nextInt();cord[i][1] = cin.nextInt();}// Dijkstraint[] dist = new int[count];boolean[] S = new boolean[count]; // 是否已将该点加入到集合S中int[] pre = new int[count];// 记录路径S[0] = true;for (int i = 1; i < count; i++) {dist[i] = distance(0, i, cord); // 起点到各点的距离pre[i] = 0;}for (int i = 1; i < count; i++) {int minDist = MAXINT;int u = 0;for (int j = 1; j < count; j++)if (!S[j] && dist[j] < minDist) {minDist = dist[j];u = j;}S[u] = true;if (u == count – 1)break;for (int j = 1; j < count; j++) {int dist_tmp = distance(u, j, cord);if (!S[j] && dist[u] + dist_tmp < dist[j]) {dist[j] = dist[u] + dist_tmp;pre[j] = u;}}}System.out.println(dist[count – 1]);cin.close();}public static int distance(int i, int j, int[][] cord) {int x = Math.abs(cord[i][0] – cord[j][0]);int y = Math.abs(cord[i][1] – cord[j][1]);return x < y ? x : y;}}

总结：

一开始用Floyd（傻了），TLE啊！！！！

后Dijkstra，单源求最短路径

一开始用数组存储计算好的各点之间的cost（傻了），OutOfMemoryError啊！！！用到再去求，还能节省时间

这一题，收获颇多

，人生就像是一场旅行，遇到的既有感人的，