首页 > 代码库 > 奇怪的电梯——看上去搜索，实际上可以直接最短路
奇怪的电梯——看上去搜索，实际上可以直接最短路
一眼望去，本来也是用的bfs，但是后来发现了是最短路。因为我打bfs 的时候想到要不要用vis 数组，就脑中模拟了一下如果访问过一层楼的话会不会有更优的情况会再次经过一次，然后想到似乎如果会再次经过的话就代表着搜索时走过了一个若干楼层构成的环，想到环就想到了最短路，最后就是这个代码。
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 using namespace std; 5 const int N=512; 6 int n,x,y,val[N]; 7 vector<int> gr[N]; 8 int dij(int sx,int tx){ 9 int dis[N];10 bool vis[N];11 for(int i=0;i<=n;i++)12 if(i==sx)dis[i]=0,vis[i]=true;13 else vis[i]=false,dis[i]=N;14 for(int i=0;i<gr[sx].size();i++)dis[gr[sx][i]]=1;15 for(int i=1;i<n;i++){16 int u=0,v=N;17 for(int j=1;j<=n;j++)18 if(!vis[j]&&dis[j]<v)19 v=dis[j],u=j;20 vis[u]=true;21 for(int j=0;j<gr[u].size();j++)22 if(!vis[gr[u][j]]&&dis[gr[u][j]]>dis[u]+1)23 dis[gr[u][j]]=dis[u]+1;24 }25 return (dis[tx]!=N?dis[tx]:-1);26 }27 int main(){28 cin>>n>>x>>y;29 for(int i=1;i<=n;i++)cin>>val[i];30 for(int i=1;i<=n;i++){31 if(i+val[i]<=n)gr[i].push_back(i+val[i]);32 if(i-val[i]>=1)gr[i].push_back(i-val[i]);33 }34 cout<<dij(x,y)<<endl;35 return 0;36 }
洛谷 0ms
奇怪的电梯——看上去搜索，实际上可以直接最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。