现在 这个也会被卡hh

4 4
1 2 1
1 3 1
3 4 1
4 3 1
1 2 2

那就改一下：

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 1010, M = 2e5 + 10;
int n, m, S, T, K;
int h[N], rh[N],e[M], w[M],ne[M], idx;
int dist[N];
bool st[N];// 每个点用没用过

void add(int h[], int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a] , h[a] = idx ++;
}
// 在反向图上dijkstra()，保存估价函数(dist[]距离)
// dist存的是该点到终点的最小距离
void dijkstra(){
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 优先队列，小根堆
    heap.push({0, T});//终点T是这里的起点 <距离，点编号>
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.y;
        if(st[ver]) continue;
        st[ver] = true;// 遍历过
        // 在反向图上遍历，rh[]数组
        for(int i = rh[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }

    }
}


int astar(){
    // 
    priority_queue<PIII,vector<PIII>, greater<PIII>> heap;
    // A* 算法，从起点开始搜
    heap.push({dist[S],{0, S}});// 估价值，{真实值，编号}
    int cnt = 0; // 终点遍历几次
    // 无解的话，返回-1

    //if(dist[S] == 0x3f3f3f3f) return -1;

    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.y.y, distance = t.y.x; //从起点到该点的真实距离
        if(ver == T) cnt ++; // 遍历一遍终点， cnt++，直到第K次
        // 这个点是终点，并且是第k短路，直接返回第k短路的真实距离distance
        if(cnt == K) return distance;

        // 正向扩展所有的边
        // 用 起点到该点的真实距离+ 该点到终点的估价距离来作为标准
        // distance + w[i] + dist[j]
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] == 0x3f3f3f3f) continue;
            heap.push({distance + w[i] + dist[j],{distance + w[i], j}});
        }
    }

    return -1;
}

int main(){
    cin >> n >> m;
    // 初始化表头
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    for(int i = 0; i < m; i ++){
        int a, b, c;
        scanf("%d%d%d",&a, &b, &c);
        add(h, a, b, c);// 建正边
        add(rh, b, a, c); // 建反边
    }
    scanf("%d%d%d",&S, &T, &K);
    if( S == T) K ++;

    dijkstra();
    cout << astar() << endl;
}

你好，为什么if(dist[j] == 0x3f3f3f3f) continue; 放在里面就可以了呢

时间有点长了，有点不太记得了，简单看了下：
1、 //if(dist[S] == 0x3f3f3f3f) return -1; 这句你可以认为是没有注释掉，表示S->T是没有道路的，是不通的，需要特判。
2、 if(dist[j] == 0x3f3f3f3f) continue;这句话的含义是：如果j->T是不通的，它再进入队列，也不可能扩展出以它为基础的通的路径，需要及时排除掉。

为什么用vector存邻接表会TLE

STL 的慢一点很正常

我使用的是vector，没有TLE。中间压入数据时，将dist=0x3f3f3f3f的点过滤掉，因为他们不会到达终点

大佬这句话heap.push({dist[S],{0, S}});// 估价值，{真实值，编号}不对吧？
应该是heap.push({dist[S],{0, S}});// 估价值 + 真实值，{真实值，编号}，只不过初始节点的真实值为0罢了！

他这里的估价值应该是指：从起点到该点的真实值+从该点到终点的估价值

为啥加那句话就能过了？最后一个数据卡无解是么

等于正无穷的话是没有路径，有1条路径就必然有k短路

不一定啊

有一条路径，你只要在那条路径上来回走就行了

那得有环路吧

可以多次走一条路的

一条路来回走

他说的是对的，只要有一条路径，就必然有第k短路，不存在的话就说明终点不连通

如果你现在再把你的代码交一遍你就不会这么说了（

如果你现在再把你的代码交一遍你就不会这么说了（

现在加上那句话也过不了了（悲

现在的数据有了自环，导致出不来了，只要设置一下当distance大于某个值，比如说max(K*L)，就break出来就行了。

加油