【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1975
【算法分析】
股价函数设为Dis(i,n)。
然后直接A*不用判重。
【其它】没有1Y。大家来BS我。。。第一次到CENA上测，90分。。。泪流满面。后来发现有个非常小的细节搞错了。。。然后这个细节如果不是刻意去搞的话，随即数据基本不可能出错，于是得了90分。
改了以后就Y了。
【CODE】
#include
using namespace std;
const int N=5005;
const int E=200005;
const int MaxL=2000005;
const double INF=1e40;
struct edge{int x,y;double w;edge *next;}g[E],*ls[N];
int n,m,e,cnt;
int L[N],v[N];
double Limit,d[N];
void addedge(int x,int y,double w){
g[++e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];
}
void init(){
int i,x,y;
double w;
e=cnt=0; clr(ls);
scanf("%d%d%lf",&n,&m,&Limit);
for (i=0;i
addedge(y,x,w);
}
}
void spfa(){
int head=0,tail=1;
for (int i=1;i<=n;i++) d[i]=INF;
clr(v);
d[n]=0; v[n]=1;
L[1]=n;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (d[t->x]+t->w
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
}
void Graph_op(){
int tmp=e;
e=0; clr(ls);
for (int i=1;i<=tmp;i++)
addedge(g[i].y,g[i].x,g[i].w);
}
struct Node{double w;int p;};
struct Heap_t{
Node a[MaxL];
int tot;
void up(int k){
while (k>1 && a[k].w
k>>=1;
}
}
void down(int k){
int p;
while ((k<<1)<=tot){
p=k<<1;
p+=(p
k=p;
}else break;
}
}
void Insert(int p,double w){
if (w>Limit) return;
tot++;
a[tot].p=p;
a[tot].w=w;
up(tot);
}
void Del(int p){
swap(a[p],a[tot]);
tot–;
down(p);
up(p);
}
}Heap;
void A_star(){
Heap.tot=0;
Heap.Insert(1,d[1]);
Node T;
while (Heap.tot && Heap.a[1].w<=Limit){
T=Heap.a[1];
Heap.Del(1);
if (T.p==n){
cnt++;
Limit-=T.w;
}
else
for (edge *t=ls[T.p];t;t=t->next)
Heap.Insert(t->y,T.w-d[T.p]+t->w+d[t->y]);
}
printf("%dn",cnt);
}
int main(){
init();
spfa();
Graph_op();
A_star();
}
