TOJ 4523 Transportation

Description
Given N stations, you want to carry goods from station 1 to station N. Among these stations, we use M tubes to connect some of them. Each tube can directly connect K stations with each other. What is the minimum number of stations to pass through to carry goods from station 1 to station N?
Input
The first line has three positive integers: N (1 ≤ N ≤ 100 000, K (1 ≤ K ≤ 1 000) and M (1 ≤ M ≤ 1 000). Then follows M lines, each line has K positive integers describing the connected stations to this tube.
Output
Output  the minimum number of stations.
If it cannot carry goods from station 1 to station N, just output -1.
Sample Input

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

Sample Output

4

Source
TOJ
 
먼저 그림을 압축해야 한다.K점이 서로 연결되어 있기 때문에 하나의 가상 점(N+i)을 도입할 수 있음을 나타낸다.
그러고 나서 실검을 해보니까 처음에 생각난 건 SPFA 같은 방법이었어.근데 나중에 직접 찾아보니까 묘하게 지나갔어.
그래서 정정이한테 물어봤어요. 왜 그래요?
나중에 생각해 보니 점 사이의 거리는 등거리이기 때문이다.만약 N까지의 거리가 비교적 길다면 틀림없이 늦게 찾은 것이다.
그러니까 먼저 돌아오는 게 제일 짧을 거야.
 

 1 #include <stdio.h>
 2 #include <iostream> 
 3 #include <queue>
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 
 7 int N,K,M;
 8 int dist[101001];
 9 int visited[101001];
10 vector<int> V[101001];
11 
12 int bfs(){
13     queue<int> Q;
14     for(int i=1; i<=N+M; i++){
15         dist[i]=inf;
16         visited[i]=0;
17     }
18     dist[1]=1;
19     visited[1]=1;
20     Q.push(1);
21     while( !Q.empty() ){
22         int u=Q.front();
23         if(u==N)return dist[u];
24         Q.pop();
25         for(int i=0; i<V[u].size(); i++){
26             int v=V[u][i];
27             if(!visited[v]){
28                 if(v<=N)
29                     dist[v]=dist[u]+1;
30                 else
31                     dist[v]=dist[u];
32                 Q.push(v);
33                 visited[v]=1;                
34             }
35         }
36     }
37     return -1;
38 }
39 
40 int main()
41 {
42     while( scanf("%d %d %d" ,&N ,&K ,&M)!=EOF ){
43         for(int i=1; i<=M; i++){
44             for(int j=0; j<K; j++){
45                 int x;
46                 scanf("%d" ,&x);
47                 V[N+i].push_back(x);
48                 V[x].push_back(N+i);
49             }    
50         }
51         int ans=bfs();
52         printf("%d
",ans);
53     }
54     return 0;
55 }