0
已解决
被禁言
新手守护
1595升降机
2
已采纳
资深天翼
这道题可以用图论写，也可以用dfs写，我用的是图论。
这是一道最短路的问题，因此我用了弗洛伊德。
一开始读入。
for i:=1 to n do
begin
if i+a[i]<=n then begin f[i,i+a[i]]:=1; end;//建一个邻接矩阵
if i-a[i]>0 then begin f[i,i-a[i]]:=1; end;//同样建一个邻接矩阵
end;
for i:=1 to n do for j:=1 to n do for k:=1 to n do if(i<>j)and(k<>j)and(k<>i)and(f[j,i]+f[i,k]<f[j,k]) then f[j,k]:=f[j,i]+f[i,k];//弗洛伊德大法好
if f[c,b]>100000 then writeln(-1) else writeln(f[c,b]);//最后判断
注意！！！f数组一开始要付很大，就像这样：
fillchar(f,sizeof(f),10000);
1
中级守护
正如他们所说
1
资深光能
广搜
1
中级守护
图论
1
高级守护
定义 n,a,b;
cin>>n>>a>>b;
for (int i=1;i<=n;++i)
{
for (int j=1;j<=n;++j)
d[i][j]=1000000;
d[i][i]=0;
}
int k;
for (int i=1;i<=n;++i)
{
scanf("%d",&k);
if (i+k<=n) d[i][i+k]=1;
if (i-k>=1) d[i][i-k]=1;
}
for (int i=1;i<=n;++i)
dis[i]=d[a][i];
int minn,t;
for (int i=1;i<=n;++i)
{
minn=1000000;
for (int j=1;j<=n;++j)
if (f[j]==0&&dis[j]<minn)
{
minn=dis[j];
t=j;
}
f[t]=1;
for (int j=1;j<=n;++j)
dis[j]=min(dis[j],dis[t]+d[t][j]);
}
if (dis[b]!=1000000)
cout<<dis[b];
else
cout<<-1;
1
高级光能
这题是图论
1
初级天翼
正如他们所说
1
高级天翼
图论
1
高级光能
变形最短路径。。。
1
高级天翼
对，就像他们所说的。
1
修练者
最短路径
1
资深守护
图论
0
中级光能
正如他们所说
0
高级天翼
图论加油！！！
