【最短路】流星雨

牛去看流星雨，不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同，求牛能否活命，如果能活命，最短的逃跑时间是多少？

注意牛可以从300以外的坐标走

1 #include <cstdio> 2 #include <iostream> 3 #include <queue> 4 #include <cstring> 5 using namespace std; 6 typedef pair<int,int> P; 7 priority_queue<P,vector<P>,greater<P> > que; 8 int n,a,b,c,ans=-1,a1,b1,m[311][311],f[311][311],reg[311][311],d[6]={0,0,1,0,-1,0}; 9 void dijkstra() 10 { 11 while(!que.empty()) 12 { 13 int x=que.top().second;que.pop(); 14 if (reg[x/1000][x%1000]==1) continue; 15 reg[x/1000][x%1000]=1; 16 if (m[x/1000][x%1000]==2000000000){ans=f[x/1000][x%1000];return;} 17 for (int i=1;i<5;i++) 18 { 19 a=x/1000+d[i],b=x%1000+d[i+1]; 20 if (a>=0&&a<311&&b>=0&&b<311&&f[a][b]>f[x/1000][x%1000]+1&&(f[x/1000][x%1000]+1<m[a][b])) 21 { 22 f[a][b]=f[x/1000][x%1000]+1; 23 que.push(P(f[a][b],a*1000+b)); 24 } 25 } 26 } 27 } 28 int main() 29 { 30 memset(f,0x7f,sizeof(f)); 31 for (int i=0;i<311;i++) for (int j=0;j<311;j++) m[i][j]=2000000000; 32 scanf("%d",&n); 33 for (int i=1;i<=n;i++) 34 { 35 scanf("%d%d%d",&a,&b,&c); 36 for (int i=0;i<5;i++) 37 { 38 a1=a+d[i],b1=b+d[i+1]; 39 if (a1>=0&&a1<311&&b1>=0&&b1<311) 40 m[a1][b1]=min(m[a1][b1],c); 41 } 42 } 43 f[0][0]=0; 44 que.push(P(0,0)); 45 dijkstra(); 46 printf("%d",ans); 47 }

 

转载于:https://www.cnblogs.com/algonote/p/7647713.html

总结

以上是生活随笔为你收集整理的【最短路】流星雨的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。