AcWing：178. 第K短路（A*）

给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。

注意：每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数N和M。

接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。

最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。

输出格式

输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出“-1”。

数据范围

1≤S,T≤N≤10001≤S,T≤N≤1000,
0≤M≤1050≤M≤105,
1≤K≤10001≤K≤1000,
1≤L≤1001≤L≤100

输入样例：

输出样例：

算法：A*

题解：预估函数是当前点到终点的距离，所以用spfa反方向跑一遍即可，利用优先队列，使当前总路径长度加上预估函数总和的最小值排序，求出第k短路即可。

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn = 1e5+;

struct node {

    int v, l, f;

    friend bool operator < (node a, node b) {

        return a.l + a.f > b.l + b.f;

    }

};

vector<pair<int, int> > g[maxn], gg[maxn];

int dis[maxn];

int vis[maxn];

int main() {

    int n, m;

    scanf("%d %d", &n, &m);

    for(int i = ; i<= m; i++) {

        int u, v, w;

        scanf("%d %d %d", &u, &v, &w);

        g[u].push_back(make_pair(v, w));    //正向建图

        gg[v].push_back(make_pair(u, w));    //反向建图

    }

    int s, t, k;

    scanf("%d %d %d", &s, &t, &k);

    for(int i = ; i <= n; i++) {

        dis[i] = INF;

    }

    dis[t] = ;

    queue<int> q;

    q.push(t);

    while(!q.empty()) {        //反向跑一遍spfa

        int u = q.front();

        q.pop();

        vis[u] = ;

        int len = gg[u].size();

        for(int i = ; i < len; i++) {

            int v = gg[u][i].first;

            int w = gg[u][i].second;

            if(dis[v] > dis[u] + w) {

                dis[v] = dis[u] + w;

                if(!vis[v]) {

                    vis[v] = ;

                    q.push(v);

                }

            }

        }

    }

    if(dis[s] == INF) {     //判断是否连通

        printf("-1\n");

        return ;

    }

    int cnt = ;

    if(s == t) {    //如果当前起点和终点重叠，则k多算一次

        k++;

    }

    priority_queue<node> pq;

    pq.push((node){s, , });

    while(!pq.empty()) {        //跑一遍A*

        node now = pq.top();

        pq.pop();

        if(now.v == t) {

            cnt++;

            if(cnt == k) {

                printf("%d\n", now.l);

                return ;

            }

        }

        int u = now.v;

        int len = g[u].size();

        for(int i = ; i < len; i++) {

            int v = g[u][i].first;

            int w = g[u][i].second;

            pq.push((node){v, w + now.l, dis[v]});

        }

    }

    printf("-1\n");        //没找到

    return ;

}

巴特西