题意:给出n个站点,每个站点都有铁路通向其他站点 如果当前要走得路恰好是该站点的开关指向的铁路,则不用扳开关,否则要手动扳动开关,给出起点和终点,问最少需要扳动多少次开关
输入的第一行是n,start,end
接下来的n行,每一行中,第一个数是该站点向外连接的铁路条数,
第二个数是该站点的开关指向的铁路(因为这儿没有读懂= =所以都建不出图来--5555参见这一句话:Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.)
所以直接指向的w=0(即为不需要扳动开关)
没有直接指向的w=1(即为需要扳动开关)
建出图来,再求最短路就可以了
因为n<=100,所以可以用floyd来做
学习的这一篇:http://blog.csdn.net/freezhanacmore/article/details/8619040
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
const int INF = ;
const int maxn=;
int d[maxn][maxn]; int main(){
int n,a,b,i,j,k,num,x;
scanf("%d %d %d",&n,&a,&b);
for(i=;i<=n;i++){ //初始化
for(j=;j<=n;j++){
if(i==j) d[i][j]=;
else d[i][j]=INF;
}
} for(i=;i<=n;i++){//建图
scanf("%d",&num);
for(j=;j<=num;j++){
scanf("%d",&x);
if(j==) d[i][x]=; else d[i][x]=;
}
} for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]); if(d[a][b]==INF) printf("-1\n");
else printf("%d\n",d[a][b]); return ;
}
第一道最短路的题目--
go--go--go