洛谷 K短路（魔法猪学院）

A*+迪杰特斯拉。。。
第十一个点卡爆
不管了

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iomanip>
#include<queue>
#define maxn 5010
#define inf 0x3f3f3f
using namespace std;
int n,m,answer,cur[maxn];
double te,d[maxn];
struct edge{///邻接表
    int to;
    double val;
    bool operator<(const edge&other)const{///改变优先级
        return val>other.val;
    }
};
vector<edge>g[maxn],gi[maxn];///g正向边gi反向边
void add_edge(int u,int v,double w)
{
    g[u].push_back((edge){v,w});///正向存边
    gi[v].push_back((edge){u,w});///反向存边
}
void dijkstra(int s){///非常正常的迪杰特斯拉
    for(int i=1;i<=n+1;i++){
        d[i]=inf;
    }
    d[s]=0;
    priority_queue<edge>q;///优先队列
    q.push((edge){s,0});///压栈
    while(!q.empty()){
        edge e=q.top();///取顶
        q.pop();
        int num=gi[e.to].size();
        for(int i=0;i<num;i++){
            if(d[gi[e.to][i].to]>d[e.to]+gi[e.to][i].val){
                d[gi[e.to][i].to]=d[e.to]+gi[e.to][i].val;///松弛操作
                q.push((edge){gi[e.to][i].to,d[gi[e.to][i].to]});///路径入栈
            }
        }
    }
}
void astar(int s){
    double maxd=te/d[s];
    priority_queue<edge>q;
    q.push((edge){s,d[s]});
    while(!q.empty()){///弹栈
        edge e=q.top();///取顶
        q.pop();///删顶
        if(e.val>te){///是否退出
            return;
        }
        if(++cur[e.to]>maxd){///到该点次数++
            continue;
        }
        if(e.to==n){///到终点累加路径长度
            te-=e.val;
            answer++;
            continue;
        }
        if(cur[e.to]>maxd){
            continue;
        }
        int num=g[e.to].size();
        for(int i=0;i<num;i++){
            q.push((edge){g[e.to][i].to,e.val-d[e.to]+g[e.to][i].val+d[g[e.to][i].to]});///保留路径入栈
        }
    }
}
int main(){
    ///freopen("read.txt","r",stdin);
    scanf("%d%d%lf",&n,&m,&te);
    while(m--){
        int s,t;
        double e;
        scanf("%d%d%lf",&s,&t,&e);
        add_edge(s,t,e);
    }
    dijkstra(n);
    astar(1);
    printf("%d\n",answer);
    return 0;
}

洛谷 K短路（魔法猪学院）

原文：https://www.cnblogs.com/snzy/p/9360552.html