首页 > 代码库 > Gym - 100851F - Froggy Ford（dijkstra）
Gym - 100851F - Froggy Ford（dijkstra）
题目链接
参考 http://blog.csdn.net/KIJamesQi/article/details/52214990
题意
蛤蛤要从这岸去到对岸，河中有n块石头，现可以在河中添加一块石头，使得在单步跳跃中的最大值最小。
分析
dijkstra应用。开两维来表示路径中是否使用过额外的石头。dis[0][u]表示没用额外石头的最大最小，dis[1][u]则表示用了额外石头的最大最小。然后用dij的思想进行转移，dis[0][u]->dis[0][u],dis[0][u]->dis[1][u],dis[1][u]->dis[1][u].
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <vector>#include <ctype.h>#include <queue>using namespace std;const int maxn=1e3+10;const int inf=0x3f3f3f3f;const int mod=1e9+7;typedef long long ll;struct point{ double x,y; void read(){ scanf("%lf%lf",&x,&y); } double operator ^(const point& rhs){ return sqrt((x-rhs.x)*(x-rhs.x)+(y-rhs.y)*(y-rhs.y)); }}a[maxn];struct Edge{ int v,nxt; double dis;}e[maxn*maxn*4];int head[maxn],tot;void init(){ memset(head,-1,sizeof(head)); tot=0;}void inline addEdge(int u,int v,double dis){ e[tot]=Edge{v,head[u],dis},head[u]=tot++; e[tot]=Edge{u,head[v],dis},head[v]=tot++;}double dis[2][maxn];int n,w;struct node{ int u; double md; bool used; point p; bool operator < (const node&rhs) const { return md>rhs.md||(md==rhs.md&& used>rhs.used); }};void diji(){ for(int i=0;i<=n+1;i++) dis[0][i]=dis[1][i]=inf; priority_queue<node> q; q.push(node{0,0,false,point{0,0}}); dis[0][0]=0; while(!q.empty()){ node t=q.top(); q.pop(); int u=t.u; if(u==n+1){ printf("%.6f %.6f\n",t.p.x,t.p.y); return; } for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v; if(v==0) continue; if(t.used){ if(dis[1][v]>max(t.md,e[i].dis)){ dis[1][v]=max(t.md,e[i].dis); q.push(node{v,dis[1][v],true,t.p}); } }else{ double x,y; if(u!=0&&v!=n+1){ x=(a[u].x+a[v].x)/2.0; y=(a[u].y+a[v].y)/2.0; } if(u==0&&v!=n+1){ x=a[v].x/2.0; y=a[v].y; } if(u!=0&&v==n+1){ x=(w+a[u].x)/2.0; y=a[u].y; } if(u==0&&v==n+1){ x=w/2.0; y=0; } if(dis[0][v]>max(t.md,e[i].dis)){ dis[0][v]=max(t.md,e[i].dis); q.push(node{v,dis[0][v],false,point{0,0}}); } if(dis[1][v]>max(t.md,e[i].dis/2.0)){ dis[1][v]=max(t.md,e[i].dis/2.0); q.push(node{v,dis[1][v],true,point{x,y}}); } } } }}int main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif freopen("froggy.in","r",stdin); freopen("froggy.out","w",stdout); scanf("%d%d",&w,&n); for(int i=1;i<=n;i++) a[i].read(); init(); int vs=0,vt=n+1; addEdge(vs,vt,w); for(int i=1;i<=n;i++){ addEdge(vs,i,a[i].x); addEdge(i,vt,w-a[i].x); for(int j=i+1;j<=n;j++) addEdge(i,j,a[i]^a[j]); } if(n==0){ printf("%.6f 0.000000\n",w/2.0); } else diji(); return 0;}
总结
对dij的思想掌握的不够啊，遇到这种题无从下手，还是太弱拉
Gym - 100851F - Froggy Ford（dijkstra）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。