Tram
Description
Tram network in Zagreb consists of a number of intersections and rails connecting some of them. In every intersection there is a switch pointing to the one of the rails going out of the intersection. When the tram enters the intersection it can leave only in the direction the switch is pointing. If the driver wants to go some other way, he/she has to manually change the switch.
When a driver has do drive from intersection A to the intersection B he/she tries to choose the route that will minimize the number of times he/she will have to change the switches manually.
Write a program that will calculate the minimal number of switch changes necessary to travel from intersection A to intersection B.
Input
The first line of the input contains integers N, A and B, separated by a single blank character, 2 <= N <= 100, 1 <= A, B <= N, N is the number of intersections in the network, and intersections are numbered from 1 to N.
Each of the following N lines contain a sequence of integers separated by a single blank character. First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection. Next Ki numbers represents the intersections directly connected to the i-th intersection.Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
Output
The first and only line of the output should contain the target minimal number. If there is no route from A to B the line should contain the integer “-1”.
Sample Input
3 2 1 2 2 3 2 3 1 2 1 2
Sample Output
0
我的代码
要求经过最少多少次换档才能从源点走到目标点，显然是用宽搜。不过求的并不是最少多少步，而是最少多少次切换，所以需要用优先队列（按切换的次数升序）来实现。
在普通的宽搜题中，可以再进队时设置flag来表示一个结点是否被访问过，但是放在这里显然是不行的，因为先进入队列的不一定是切换次数最少的情况。
我的第一次尝试是当一个十字路口出队且完成结点拓展后再设置其标记位。出队时如果标记位为1就不需要考虑。但是显然在最开始的时候任何一个结点会无限制地进队，事实证明的确超时了。
q.push(node(a,0));
while(true){
node temp=q.top();
q.pop();
if (temp.inter==b){
ans=temp.step;
break;
}
if(flag[temp.inter]==1){
continue;
}
for (int i=0;i<v[temp.inter].size();i++){
if (flag[v[temp.inter][i]]==0){
if (i==0){
q.push(node(v[temp.inter][i],temp.step));
}else{
q.push(node(v[temp.inter][i],temp.step+1));
}
}
}
flag[temp.inter]=1;
}最终解法时将标记位初始化为无穷大，只有当访问该结点时使用的操作次数比标记位小时才可入队，并且同时更新标记位。这一次的用时几乎可以忽略不记了。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;
struct node{
int inter;
int step;
node(){}
node(int inter,int step):inter(inter),step(step){}
bool operator<(const node a)const{
return step>a.step;
}
};
int n,a,b,num,t,ans;
int flag[101];
priority_queue<node> q;
vector<int> v[101];
int main()
{
while (!q.empty()) q.pop();
scanf("%d%d%d",&n,&a,&b);
for (int i=1;i<=n;i++){
scanf("%d",&num);
v[i].clear();
flag[i]=0x3f3f3f3f;
for (int j=0;j<num;j++){
scanf("%d",&t);
v[i].push_back(t);
}
}
q.push(node(a,0));
flag[a]=0;
while(true){
if (!q.empty()){
node temp=q.top();
q.pop();
if (temp.inter==b){
ans=temp.step;
break;
}
for (int i=0;i<v[temp.inter].size();i++){
if (i==0){
if (flag[v[temp.inter][i]]>temp.step){
q.push(node(v[temp.inter][i],temp.step));
flag[v[temp.inter][i]]=temp.step;
}
}else{
if (flag[v[temp.inter][i]]>temp.step+1){
q.push(node(v[temp.inter][i],temp.step+1));
flag[v[temp.inter][i]]=temp.step+1;
}
}
}
}else{
ans=-1;
break;
}
}
printf("%d\n",ans);
return 0;
}