[5214] 환승

환승 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	952	211	156	24.111%

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최소값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

예제 입력 

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

예제 출력 

4

힌트

N을 입력받았다면 하이퍼튜브의 좌표를 N + 1부터 N + M + 1까지라고 생각했습니다.

하이퍼튜브와 일반 정점의 차이는 cost입니다.

하이퍼튜브로 가는 비용은 0이고 다른 정점으로 가는 비용은 1입니다.

그리고 다익스트라를 이용해서 N까지의 최소비용을 구하면 간단하게 해결할 수 있습니다.

#include <iostream>
#include <cstdio>
 
#include <algorithm>
#include <string.h>
 
#include <stack>
#include <vector>
#include <queue>
 
#define MAX_SIZE 102000
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define INF 0x7fffffff
 
using namespace std;
typedef pair<int, int> p;
 
vector<int> v[MAX_SIZE];
 
int n, k, m;
int dist[MAX_SIZE];
bool visit[MAX_SIZE];
int pos;
 
 
 
void dijkstra()
{
    for(int i = 2; i < pos; i++) dist[i] = INF;
 
    priority_queue<p> pq; // - 로 값을 넣자
    pq.push(mp(-1, 1));
 
    while(!pq.empty())
    {
        p pop_data = pq.top();
        pq.pop();
 
        int from = pop_data.second;
        int cnt = -pop_data.first;
 
        if(visit[from]) continue;
        visit[from] = 1;
 
        for(int i = 0; i < v[from].size(); i++)
        {
            int to = v[from][i];
            int add = 1;
 
            if(to > n) add--; // 하이퍼 튜브면 -를 해서 cost를 0로 만든다.
 
            if(dist[to] > cnt + add)
            {
                dist[to] = cnt + add;
                pq.push(mp(-dist[to], to));
            }
        }
    }
}
 
 
int main()
{
    scanf("%d %d %d", &n, &k, &m);
 
 
    pos = n + 1; // 하이퍼튜브 좌표
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < k; j++)
        {
            int to;
            scanf("%d", &to);
            v[pos].push_back(to);
            v[to].push_back(pos);
        }
 
        pos++;
    }
 
    dijkstra();
    printf("%d\n", dist[n] == INF ? -1 : dist[n]);
    return 0;
}