POJ 1847

• 思路：每一个点都有多个出路,默认指出一条,问是否有最少转化次数到达终点,
• 条件转化为,原点的第一条边的权值为0,其余出边的权值为1,等价于转换开关的次数.
• 最短路模板

  #include <iostream>
  #include <queue>
  #include <string.h>
  using namespace std;
  const int maxn = 105;
  
  int e[maxn][maxn];
  int n,m,start,end;
  int dist[maxn];
  bool vis[maxn];
  
  int spfa() {
  	queue<int> que;
  	memset(dist,0x3f,sizeof dist);
  	memset(vis,0,sizeof vis);
  	que.push(start);
  	vis[start] = 1; dist[start] = 0;
  
  	while (!que.empty()) {
  		int cur = que.front(); que.pop();
  		vis[cur] = 0;
  		for (int i=1; i<=n; i++) {
  			if (dist[i] > dist[cur] + e[cur][i]) {
  				dist[i] = dist[cur] + e[cur][i];
  				if (!vis[i]) {
  					vis[i] = 1;
  					que.push(i);
  				}
  			}
  		}
  	}
  	return dist[end];
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	cin >> n >> start >> end;
  	int k,backup,cur;
  	memset(e,0x3f,sizeof e);
  	for (int i=1; i<=n; i++) {
  		cin >> k; backup = k;
  		while (k--) {
  			cin >> cur;
  			if (k == backup-1) {
  				e[i][cur] = 0;
  			}
  			else e[i][cur] = 1;
  		}
  	}
  	int ans = spfa();
  	if (ans == 0x3f3f3f3f) printf("-1",ans);
  	else printf("%d",ans);
  	return 0;
  }