返回信息流题目3 : 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 Xi and Yi.
For 40% data, N<=1000，0<=Xi,Yi<=100000.
For 100% data, N<=100000，0<=Xi,Yi<=1000000000.
输出
Output the minimum cost.
样例输入
3
2 2
1 7
7 6
样例输出
2
我的思路是：建图，然后Floyd来求最短路径。但是TLE了。求大神告知如何做。这个图是对称的，该怎么利用这个性质。附上我的代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[][] island = new int[N][2];
for (int i = 0; i < N; i++) {
island[i][0] = in.nextInt();
island[i][1] = in.nextInt();
}
int[][] G = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
G[i][j] = distance(i, j, island);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (G[i][j] > G[i][k] + G[k][j]) {
G[i][j] = G[i][k] + G[k][j];
}
}
}
}
System.out.println(G[0][N - 1]);
in.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;
}
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89384同步于 2016/3/29
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
微软去年的这道题怎么做。
lee123
2016/3/29镜像同步21 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
http://hihocoder.com/problemset/problem/1138
要是AC了记得给我一下代码。
【 在 Wizmann 的大作中提到: 】
: 不发链接谁帮你做啊。。。
对对。你说的对。他两个一起出现。我记忆错了。我只记得floyd优化了dijkstra。优化的是代码简洁。而不是其他。再次感谢。
【 在 chenxiansf 的大作中提到: 】
: o平方呀，flyod才是o三方
刚好去年做微软。。
随便一个最短路算法就行了，dijk、spfa什么的都可以，主要是想清楚一件事，每个点的连接点其实只要算四个就可以了，不用把所有其他的点都算上，复杂度就下来了。
【 在 lee123 的大作中提到: 】
: 题目3 : Islands Travel
: 时间限制:10000ms
: 单点时限:1000ms
: ...................
嗯嗯。我用了dijk还是TLE。n那么大，边要爆了。
为什么只要算四个？不懂。
【 在 heifrank 的大作中提到: 】
: 刚好去年做微软。。
: 随便一个最短路算法就行了，dijk、spfa什么的都可以，主要是想清楚一件事，每个点的连接点其实只要算四个就可以了，不用把所有其他的点都算上，复杂度就下来了。
: