# 17940 지하철

문제 : <https://www.acmicpc.net/problem/17940>

```python
from collections import deque
def bfs(stn):
    Q = deque()
    Q.append(stn)
    while Q:
        stn = Q.popleft()
        for next, time in graph[stn]:
            # 환승 정보 초기화
            new_trans=dp[stn][0]
            new_time=dp[stn][1]+time
            next_trans = dp[next][0]
            if cpn[stn] != cpn[next]:
                new_trans+=1
            # 환승 횟수가 적거나 같으면 갱신, 아니면 넘어가기
            if new_trans > next_trans or new_trans > dp[M][0]:
                continue
            elif new_trans < next_trans:
                dp[next] = [new_trans, new_time]
            else: # 환승 횟수가 같고 시간이 적으면
                if new_time < dp[next][1]:
                    dp[next][1] = new_time
                else:
                    continue
            # 도착한거 아니면 다음으로
            if next != M:
                Q.append(next)
            
N,M=map(int,input().split()) # N:지하철역 개수, M: 도착지 번호
cpn=[0]*N # 지하철역 운영 회사 정보 (역은 0부터 N-1까지)
graph=[[] for _ in range(N)]
dp=[[float('inf'),float('inf')] for _ in range(N)]
dp[0]=[0,0]
for i in range(N):
    cpn[i]=int(input())
for i in range(N):
    temp=list(map(int,input().split()))
    for stn, time in enumerate(temp):
        if time != 0:
            graph[i].append((stn,time))
bfs(0)
print(dp[M][0],dp[M][1]) # 환승 횟수, 소요 시간 출력
```

다익스트라인줄 모르고 꾸역꾸역 dp bfs로 풀었다. (dfs는 통과 안됨)

당연히 다익스트라로 푼 것보다 2-3배 정도 느림.

통과는 했지만 문제가 다익스트라를 사용하는지 안 하는지를 캐치해야 한다는 걸 배웠다.

```python
import sys, heapq
input = sys.stdin.readline
INF = 10 ** 6

N, M = map(int, input().split())
company = []
time = []
for _ in range(N):
    company.append(int(input()))
for _ in range(N):
    time.append(list(map(int, input().split())))
info = [10 ** 8 for _ in range(N)]
q = []
heapq.heappush(q, (0, 0))
info[0] = 0
while q:
    t, k = heapq.heappop(q)
    if info[k] < t:
        continue
    for i in range(N):
        if time[k][i]:
            is_tf = (company[k] != company[i])
            new_t = t + time[k][i] + INF * is_tf
            if new_t < info[i]:
                info[i] = min(info[i], new_t)
                heapq.heappush(q, (info[i], i))
print(info[M] // INF, info[M] % INF)
```

다른 사람이 짠 정석 코드.

<https://www.acmicpc.net/source/69544741>

<https://techblog-history-younghunjo1.tistory.com/248>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/17940.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.