[백준|파이썬] Игра

0. 문제

https://www.acmicpc.net/problem/29687

29687번: Игра

 

문제 해석

두 명의 플레이어가 새로운 보드 게임을 하고 있습니다. 
경기장에는 도시와 도시 사이에 도로가 있으며, 도시마다 도로의 길이가 다를 수 있습니다. 
또한 두 도시 사이의 도로 길이가 x라면 이 도로에는 (x-1)개의 마을이 연속적으로 있으므로 
도시에서 도로의 가장 바깥쪽 마을로, 이 마을에서 이웃 마을로 갈 수 있습니다.
각 플레이어는 칩을 가지고 있으며, 처음에는 플레이어 칩이 다른 도시에 위치합니다. 
플레이어는 차례대로 진행합니다. 
한 번의 이동으로 조각을 현재 정점에 직접 연결된 도시나 마을로 이동할 수도 있고 
조각을 제자리에 둘 수도 있습니다. 
첫 번째 플레이어가 시작됩니다.
그러나 한 가지 제한 사항이 있습니다. 
플레이어 중 한 명이 두 도시 사이의 도로에 있는 마을 중 하나에 있으면 다른 플레이어는 
이 도로에 있는 어떤 마을에도 갈 수 없습니다.
각 플레이어의 목표는 수도에 먼저 도착하는 것입니다.
입력 입력 파일의 첫 번째 줄에는 두 개의 숫자 n 도시 수와 m 도로 수(1 =< n,m=< 10^5)가 포함됩니다.
다음 m개 줄에는 세 개의 숫자 a, b, c가 포함되어 있습니다. 
이는 도시 a와 b 사이에 c-1개의 마을(a=!b, 1=<c=< 10^9)을 포함하는 c 길이의 도로가 있음을 의미합니다.
마지막 줄에는 세 개의 숫자 s_1, s_2--- 플레이어의 조각이 처음 위치한 도시의 번호(s_1 != s_2) 및
t --- 수도인 도시의 번호가 포함됩니다.
모든 도시의 도로가 다른 도시로 연결될 수 있다는 것이 보장됩니다.
산출 출력 파일에서 첫 번째 플레이어가 해당 항목에 도달하면 First를 인쇄합니다. 
대문자가 먼저이고, 두 번째이면 Second입니다.
플2수도ㅡ마을ㅡ마을ㅡ도시|           도로 -> 길이 다를수 있음|          
도로 길이 x 이면 마을이 x-1개|도시플1플레이어 중 한 명이 두 도시 사이의 도로에 있는 마을 중 하나에
있으면 다른 플레이어는 이 도로에 있는 어떤 마을에도 갈 수 없습니다. 
각 플레이어의 목표는 수도에 먼저 도착하는 것

 

1. 풀이

이런 경우가 있을수 있다.
Player1과 Player2가 가다가 도시에서 마주치는 경우와 안 마주치는 경우


1. 두 player가 한 도시에서 동시에 만나는 경우
	- player2가 미리 도착했다. 그래서 다른 player(player1)가 우회해서 가는 경우
	- player2가 미리 도착했다. 그래서 다른 player(player1)가 잠깐 멈췄다 가는 경우
2. 두 player가 안 만나는 경우

1에서도 어차피 빨리 오는 player2가 이깁니다. 
2에서는 빨리 오는 player가 이깁니다.

결국 빨리 오는 player가 이기고, 동시에 도착한다면 player1이 먼저 시작했기 때문에 player1이 도착한다.

 

2. 코드

import heapq
import sys
input = sys.stdin.readline
N, M = map(int,input().rstrip().split())

adj = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int,input().rstrip().split())
    adj[a].append((b,c))
    adj[b].append((a,c))

s1, s2, capital = map(int,input().rstrip().split())

def dijkstra(start):
    distances = [float('inf') for _ in range(N+1)]
    # 최단경로로 가는 방법을 기록할 것 => index 로 가는 가장 빠른 방법은 nearest_path[index]
    hq = []
    heapq.heappush(hq, (0, start))
    distances[start] = 0 
    while hq:
        dist, now = heapq.heappop(hq)
        if distances[now] < dist: continue  # 원천 봉쇄
        for i in adj[now]:
            next_node = i[0]
            cost = dist + i[1]
            if cost < distances[next_node]:
                distances[next_node] = cost
                heapq.heappush(hq, (cost, next_node))
    return distances


distances= dijkstra(capital)
# print(distances)
if distances[s1]<=distances[s2]: print("First")
else: print("Second")

3. 실수

 

제발 아래 초기화 코드를 잊지 말자ㅠㅠㅠ

    distances[start] = 0