PKU 2394---Checking an Alibi
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 3854
Accepted: 1384
Description
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.
Input
* 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.
Output
* 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.
Sample Input
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
Sample Output
4
1
2
3
4
Hint
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.
Source
USACO 2005 March Silver
제목 대의:
한 곳에는 ffarm이 있는데 각각 f1, f2,......fp.그중 f1은 곡창!C마리의 소가 이 농장에서 곡창에 가서 곡식을 훔쳐 먹으려고 한다.근데 방금 어떤 카메라가 곡식을 먹기 전 M초 위치를 찍었어요.그리고 이farm 사이에는 P개의 경로가 있다는 것을 알고 있습니다. 예를 들어fi와 fj 사이에는 경로가 연결되어 있고 이 경로를 걷는 시간time(fi와 fj 사이에 여러 개의 경로가 있을 수 있음)을 알고 있습니다.지금 C두 소의 M초 전 위치를 알려주고 곡식을 훔쳐 먹을 수 있는 소의 위치를 출력하라고 합니다(입력한 선후 순서에 따라 출력).
문제 풀이 사고방식: 뚜렷한 최단 경로 문제, Dijstra 알고리즘을 사용합니다.
AC 코드:
Accepted
1160K
0MS
C++
1063B
2010-11-10 21:31:57
#include
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.