A* 过不了，如果你只是想拿部分分当我没说。
by Yusani_huh @ 2022-10-30 17:19:56
@[Yanusi_huh](/user/239895) 我想试试就逝世
by YuRuochen @ 2022-10-30 17:22:08
@[Yanusi_huh](/user/239895) 或许您可以帮我调调代码。。。
by YuRuochen @ 2022-10-30 17:22:29
@[YuRuochen](/user/658786) 但是我不会 A*（dbq
by Yusani_huh @ 2022-10-30 17:23:02
@[Yanusi_huh](/user/239895) 最新的CODE:
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
double e,dis[5010],sum;
bool vis[5010];
vector<pair<int,double> > a[5010],b[5010];
queue<int> q;
struct node{
int t;
double S,F;
void init(int a,double b){
t=a;
S=b;
F=b+dis[a];
}
friend bool operator<(const node &x,const node &y){
return x.F<y.F;
}
};
priority_queue<node> sq;
void SPFA(int start){
memset(dis,127,sizeof(dis));
vis[start]=1;
dis[start]=0;
q.push(start);
while(!q.empty()){
int now=q.front();
vis[now]=0;
for(int i=0;i<b[now].size();i++){
double s=dis[now]+b[now][i].second;
int t=b[now][i].first;
if(s<dis[t]){
dis[t]=s;
if(!vis[t]){
vis[t]=1;
q.push(t);
}
}
}
q.pop();
}
}
int main(){
scanf("%d%d%lf",&n,&m,&e);
while(m--){
int u,v;
double w;
scanf("%d%d%lf",&u,&v,&w);
a[u].push_back(make_pair(v,w));
b[v].push_back(make_pair(u,w));
}
SPFA(n);
node start;
start.init(1,0);
sq.push(start);
while(!sq.empty()){
node now=sq.top();
sq.pop();
int t=now.t;
double S=now.S;
if(t==n){
sum+=S;
if(sum>e) break;
ans++;
}else{
for(int i=0;i<a[t].size();i++){
int p=a[t][i].first;
double g=S+a[t][i].second;
if(g+dis[p]>e) continue;
node o;
o.init(p,g);
sq.push(o);
}
}
}
printf("%d",ans);
return 0;
}
```
by YuRuochen @ 2022-10-30 17:23:57
@[Yanusi_huh](/user/239895) 现在100分，MLE了。。。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
double e,dis[5010],sum;
bool vis[5010];
vector<pair<int,double> > a[5010],b[5010];
queue<int> q;
struct node{
int t;
double S,F;
void init(int a,double b){
t=a;
S=b;
F=b+dis[a];
}
friend bool operator<(node x,node y){
return x.F>y.F;
}
};
priority_queue<node> sq;
void SPFA(int start){
memset(dis,127,sizeof(dis));
vis[start]=1;
dis[start]=0;
q.push(start);
while(!q.empty()){
int now=q.front();
vis[now]=0;
for(int i=0;i<b[now].size();i++){
double s=dis[now]+b[now][i].second;
int t=b[now][i].first;
if(s<dis[t]){
dis[t]=s;
if(!vis[t]){
vis[t]=1;
q.push(t);
}
}
}
q.pop();
}
}
int main(){
scanf("%d%d%lf",&n,&m,&e);
while(m--){
int u,v;
double w;
scanf("%d%d%lf",&u,&v,&w);
a[u].push_back(make_pair(v,w));
b[v].push_back(make_pair(u,w));
}
SPFA(n);
node start;
start.init(1,0);
sq.push(start);
while(!sq.empty()){
node now=sq.top();
sq.pop();
int t=now.t;
double S=now.S;
if(t==n){
sum+=S;
if(sum>e) break;
ans++;
}else{
for(int i=0;i<a[t].size();i++){
int p=a[t][i].first;
double g=S+a[t][i].second;
if(g+dis[p]>e) continue;
node o;
o.init(p,g);
sq.push(o);
}
}
}
printf("%d",ans);
return 0;
}
```
by YuRuochen @ 2022-10-30 17:27:59
@[YuRuochen](/user/658786) MLE 了就是被卡了，其他的我不知道因为我真的不会 A*，别 at 我了（
by Yusani_huh @ 2022-10-30 17:31:07
@[YuRuochen](/user/658786) 这道题卡A*，为什么不用可持久化可并堆和Dj呢
by _zexal_ @ 2023-03-11 13:32:25
@[zhong114514](/user/754856) 因为我不会
by YuRuochen @ 2023-03-12 08:30:45
@[YuRuochen](/user/658786) 您可以学。
by 北射天狼 @ 2023-04-04 22:23:48