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
先要对图进行压缩。因为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\n",ans); 53 } 54 return 0; 55 }
TOJ 4523 Transportation,布布扣,bubuko.com
原文：http://www.cnblogs.com/chenjianxiang/p/3592907.html