[Sdoi2010]魔法猪学院 【A*搜索】【堆】【K短路】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1975
【算法分析】
股价函数设为Dis(i,n)。
然后直接A*不用判重。
【其它】没有1Y。大家来BS我。。。第一次到CENA上测，90分。。。泪流满面。后来发现有个非常小的细节搞错了。。。然后这个细节如果不是刻意去搞的话，随即数据基本不可能出错，于是得了90分。
改了以后就Y了。
【CODE】
#include #include #include #include #define clr(a) memset(a,0,sizeof(a))
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 scanf("%d%d%lf",&x,&y,&w);
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 d[t->y]=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 swap(a[k],a[k>>1]);
k>>=1;
}
}

void down(int k){
int p;
while ((k<<1)<=tot){
p=k<<1;
p+=(p if (a[p].w swap(a[p],a[k]);
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();
}