1 solutions
-
0
C++ :
#include <iostream> #include <algorithm> using namespace std; const int N(202),oo(0x6fffffff); int g[N][N],dist[N]; bool judge[N]={false}; int main() { int n,a,b; cin>>n>>a>>b; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) g[i][j]=oo; int x; for(int i=1;i<=n;i++) { cin>>x; if(i+x<=n) g[i][i+x]=1; if(i-x>=1) g[i][i-x]=1; } for(int i=1;i<=n;i++) dist[i]=g[a][i]; judge[a]=true; for(int i=1;i<=n-1;i++) { int p,minx(oo); for(int t=1;t<=n;t++) if(minx>dist[t]&&judge[t]==false) minx=dist[t],p=t; judge[p]=true; for(int j=1;j<=n;j++) if(!judge[i]) dist[j]=min(g[p][j]+dist[p],dist[j]); } cout<<dist[b]<<endl; return 0; }
- 1
Information
- ID
- 18997
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By