首页 > 代码库 > BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨
BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1611
解:直接广搜。。。
程序:
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #define maxn 210000000 using namespace std; int ans; int f[500][500]; bool vis[500][500]; int h[5]={0,-1,1,0,0},l[5]={0,0,0,-1,1}; struct ding{ int x,y,t; }; queue<ding>q; bool check(int x,int y) { if ((x<0)||(y<0)) return false; return true; } int main() { int m;scanf("%d",&m); for (int i=0;i<=400;i++) for (int j=0;j<=400;j++) f[i][j]=maxn; int x1,y1,t1; for (int i=1;i<=m;i++) { scanf("%d%d%d",&x1,&y1,&t1); for (int j=0;j<=4;j++) if (check(x1+h[j],y1+l[j])) f[x1+h[j]][y1+l[j]]=min(f[x1+h[j]][y1+l[j]],t1); } q.push((ding){0,0,0}); vis[0][0]=true; while (!q.empty()) { ding now=q.front(); q.pop(); if (f[now.x][now.y]==maxn) { printf("%d\n",now.t); return 0; } for (int i=1;i<=4;i++) if (check(now.x+h[i],now.y+l[i])) if (f[now.x+h[i]][now.y+l[i]]>now.t+1) if (!vis[now.x+h[i]][now.y+l[i]]) { vis[now.x+h[i]][now.y+l[i]]=true; q.push((ding){now.x+h[i],now.y+l[i],now.t+1}); } } printf("-1\n"); return 0; }
BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。