Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26943 Accepted Submission(s): 9699
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cstdlib> #include <iomanip> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define ios() ios::sync_with_stdio(false) #define INF 0x3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int dis[250],g[250][250],vis[250]; int a[250],n,x,y,k; void init() { for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { g[i][j]=g[j][i]=INF; } g[i][i]=0; } } void dij(int x) { for(int i=1;i<=n;i++) { dis[i]=g[x][i]; vis[i]=0; } vis[x]=1; int minn,v=x; for(int i=1;i<n;i++) { minn=INF; for(int j=1;j<=n;j++) { if(!vis[j] && minn>dis[j]) { minn=dis[j]; v=j; } } if(minn==INF) break; vis[v]=1; for(int j=1;j<=n;j++) { if(!vis[j]) dis[j]=min(dis[j],dis[v]+g[v][j]); } } } int main() { while(scanf("%d",&n)&&n) { init(); scanf("%d%d",&x,&y); for(int i=1;i<=n;i++) { scanf("%d",&k); if(i-k>=1) g[i][i-k]=1; if(i+k<=n) g[i][i+k]=1; } dij(x); printf("%d\n",dis[y]==INF?-1:dis[y]); } return 0; }
bfs
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cstdlib> #include <iomanip> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define ios() ios::sync_with_stdio(false) #define INF 0x3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int vis[250],x,n; int dis[250],y,xx; struct node { int x; int step; }ans,pos; int bfs(int A,int B) { queue<node>q; memset(vis,0,sizeof(vis)); vis[A]=1; pos.x=A;pos.step=0; q.push(pos); while(!q.empty()) { pos=q.front(); q.pop(); if(pos.x==B) return pos.step; xx=pos.x+dis[pos.x]; if(x<=n && !vis[xx]) { ans.x=xx; ans.step=pos.step+1; vis[xx]=1; q.push(ans); } xx=pos.x-dis[pos.x]; if(x>=1 && !vis[xx]) { ans.x=xx; ans.step=pos.step+1; vis[xx]=1; q.push(ans); } } return -1; } int main() { while(scanf("%d",&n)&&n) { scanf("%d%d",&x,&y); for(int i=1;i<=n;i++) { scanf("%d",&dis[i]); } printf("%d\n",bfs(x,y)); } return 0; }
HDU 1548 A strange lift(最短路&&bfs)
原文:http://www.cnblogs.com/shinianhuanniyijuhaojiubujian/p/7275094.html