选了8个素数...压力略大......

不会写Floyd只会写Dijs不用考虑重边

#include<cstdio>
#include<cmath>
#include<algorithm>
#define precision 0.0001
#define maxn 1000
using namespace std;
struct tnode{double d,p;}a[maxn+10];
double d1,c,d2,p;
int n;
bool cmp(tnode xx,tnode yy)
{
return xx.d<yy.d;
}
int main()
{
// freopen("lyuxing.in","r",stdin);
// freopen("lyuxing.out","w",stdout);
int i,j,k; double s,ans,x,y;
scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n);
a[1].d=0,a[1].p=p;
a[2].d=d1,a[2].p=0;
for(n+=2,i=3;i<=n;i++)scanf("%lf%lf",&a[i].d,&a[i].p);
sort(a+1,a+n+1,cmp);
k=1,ans=x=0,s=c*d2;
while(k<=n)
{
if(a[k+1].d-a[k].d>s){printf("No Solution\n");return 0;}
for(j=k+1;a[j].d-a[k].d<=s && j<=n;j++)
if(a[j].p<=a[k].p)
{
y=(a[j].d-a[k].d)/d2;
if(x<y)ans+=a[k].p*(y-x),x=0;
else x-=y;
k=j;
break;
}
if(fabs(a[k].d-d1)<=precision)
{
printf("%.2lf\n",ans);
return 0;
}
if(j!=k)
{
ans+=a[k].p*(c-x);
x=c-(a[k+1].d-a[k].d)/d2;
k++;
}
}
return 0;
}

回复 @name :
哥们你是可以重评的，不必交这么多遍...

坑正确率的题目。。。

用dfs写了个离线动态生成树，结果看别人的代码都是在线暴力并查集= =

Orz..这模型厉害。。。

神一般的位运算……然而还是没有完全参透，明天一定再看看……

这题真可以用随机化！！！模拟退火大法好！！！！！！！

写着写着忘取模了。。。。。。

膜拜叶子大神, 思路果然清新飘逸.

回复 @Alboi_真神名曰��蛋蛋 :
大神求教

数据水，rand()乱搞过了

随机化多交几次就过了

我只是想刷刷水题来着……

无脑树剖代码题1A之。。。。复制粘贴大法好，20分钟搞完360行代码。

正解其实是暴力DFS寻找所有可能路径加个剪枝->_->