首页 > 数据结构 > Hash表 > POJ 2394 Checking an Alibi [解题报告] Java
2013
11-11

POJ 2394 Checking an Alibi [解题报告] Java

Checking an Alibi

问题描述 :

A crime has been comitted: a load of grain has been taken from the barn by one of FJ’s cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain.

Farmer John’s farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths).

Given the layout of Farmer John’s farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty.

NOTE: Do not declare a variable named exactly ‘time’. This will reference the system call and never give you the results you really want.

输入:

* Line 1: Four space-separated integers: F, P, C, and M

* Lines 2..P+1: Three space-separated integers describing a path: F1,F2, and T. The path connects F1 and F2 and requires T seconds to traverse.

* Lines P+2..P+C+1: One integer per line, the location of a cow. The first line gives the field number of cow 1, the second of cow 2, etc.

输出:

* Line 1: A single integer N, the number of cows that could be guilty of the crime.

* Lines 2..N+1: A single cow number on each line that is one of the cows that could be guilty of the crime. The list must be in ascending order.

样例输入:

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

样例输出:

4
1
2
3
4

温馨提示:

INPUT DETAILS:

Fields/distances like this:

          6

4------5
| |
2| |
| |
7-----1 |5
9 | |
1| |
| |
2------3

OUTPUT DETAILS:

Any cow except cow 5 could have done it. Cow 5 would take 9 seconds to get to the barn.

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;
public class Main 
{
	public static int mat[][]=new int[505][505];
	public static int d[]=new int[505];
	public static void main(String args[]) throws Exception {
		Scanner cin=new Scanner(System.in);
		int F,P,C,M;
		int i,j,k;
		int a,b,c;
		F=cin.nextInt();
		P=cin.nextInt();
		C=cin.nextInt();
		M=cin.nextInt();
		for(i=0;i< F;++i)
		  for(j=0;j< F;++j)
		    mat[i][j]=i==j?0:1000000000;
		while(P>0)
		{
			--P;
			a=cin.nextInt();
			b=cin.nextInt();
			c=cin.nextInt();
			--a;
			--b;
			if(c< mat[a][b])
				mat[a][b]=mat[b][a]=c;
		}
		for(i=0;i< F;++i)d[i]=1000000000;
		d[0]=0;
		boolean v[]=new boolean[505];
		Arrays.fill(v, false);
		for(i=0;i< F;++i)
		{
			k=-1;
			for(j=0;j< F;++j)
		           if(!v[j]&&(k==-1||d[j]< d[k]))k=j;
			for(v[k]=true,j=0;j< F;++j)
			   if(!v[j]&&d[k]+mat[k][j]< d[j])
				d[j]=d[k]+mat[k][j];
		}
		int hash[]=new int[505];
		Arrays.fill(hash, -1);
		for(i=0;i< C;++i)
		{
			c=cin.nextInt();
			--c;
			hash[i]=c;
		}
		int ans=0;
		for(i=0;i< C;++i)
			if(hash[i]!=-1&&d[hash[i]]<=M)
				++ans;
		System.out.println(ans);
		for(i=0;i < C;++i)
			if(hash[i]!=-1&&d[hash[i]]<=M)
				System.out.println(i+1);
	}
}

  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  2. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  4. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  5. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。