FZU 1635 Commandos
Commandos
Time Limit:1s
Memory limit:32M
Accepted Submit:42
Total Submit:58
A group of commandos were assigned a critical task. They are to destroy an enemy head quarter. The enemy head quarter consists of several buildings and the buildings are connected by roads. The commandos must visit each building and place a bomb at the base of each building. They start their mission at the base of a particular building and from there they disseminate to reach each building. The commandos must use the available roads to travel between buildings. Any of them can visit one building after another, but they must all gather at a common place when their task in done. In this problem, you will be given the description of different enemy headquarters. Your job is to determine the minimum time needed to complete the mission. Each commando takes exactly one unit of time to move between buildings. You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.
Input
The first line of input contains a number T<50, where T denotes the number of test cases. Each case describes one head quarter scenario. The first line of each case starts with a positive integer N≤100, where N denotes the number of buildings in the head quarter. The next line contains a positive integer R, where R is the number of roads connecting two buildings. Each of the next R lines contain two distinct numbers, 0 ≤ u,v < N, this means there is a road connecting building u to building v. The buildings are numbered from 0 to N-1. The last line of each case contains two integers 0 ≤ s,d < N. Where s denotes the building from where the mission starts and d denotes the building where they must meet.
You may assume that two buildings will be directly connected by at most one road. The input will be such that, it will be possible to go from any building to another by using one or more roads.
Output
For each case of input, there will be one line of output. It will contain the case number followed by the minimum time required to complete the mission. Look at the sample output for exact formatting.
Sample Input
2
4
3
0 1
2 1
1 3
0 3
2
1
0 1
1 0
Sample Output
Case 1: 4
Case 2: 1
Original: Summer Training I--Graph
문제 풀기:
제목이 꽤 길어요. 돌격대가 건물을 폭파하러 간 이야기일 거예요.사고방식이 분명하다. 돌격대 안에 한 무리의 사람들이 있는데, 각자 건물 목표가 있을 때만 폭파하고 함께 종점 목표로 돌아간다.구도 사상은 먼저 기점에서 나머지 각 점 건축물까지의 최단 경로를 구하고 나머지 점에서 종점까지의 최단 경로를 구한다.마지막으로 도착한 그 사람이 총 시간을 결정했다.Floyd 알고리즘 풀이, 코드는 다음과 같습니다.
#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에 따라 라이센스가 부여됩니다.