问个问题，有关KSP

常规
1

Astar如何保存路径？

2

记录前缀吧

3

but whywhywhy

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define PA pair<int, int>
using namespace std;


const int MAX = 10005;
vector<PA> G[MAX];
vector<PA> RG[MAX];
int h[MAX], cnt[MAX];
int dis[MAX];
int n, m, k, s, t;
//f:u s:dist
struct Node
{
    int first, second;
    vector<int> Path;
    Node (int _, int __) : first(_), second(__) {}
    Node (int _, int __, vector<int> ___) : first(_), second(__), Path(___) {}
    bool operator < (Node x) const
    {
        return second + h[first] > x.second + h[x.first];
    }
};

void Rdijkstra()
{
    priority_queue<Node> Q;
    memset(h, 0x3f, sizeof h);
    Q.push(Node(t, 0));
    h[t] = 0;
    while (!Q.empty())
    {
        auto now = Q.top(); Q.pop();
        int u = now.first, d1 = now.second;
        if (d1 > h[u])
        {
            continue;
        }
        for (auto nxt : RG[u])
        {
            int v = nxt.first, c = nxt.second;
            if (h[v] > h[u] + c)
            {
                h[v] = h[u] + c;
                Q.push(Node(v, h[v]));
            }
        }
    }
}

bool flag = 0;
void AS()
{
    priority_queue<Node> Q;
    memset(dis, 0x3f, sizeof dis);
    vector<int> tmp; tmp.push_back(s);Q.push(Node(s, 0, tmp));
    
    while (!Q.empty())
    {
        auto now = Q.top(); Q.pop();
        int u = now.first, g = now.second;
        cnt[u]++;
        if (u == t && cnt[u] == k)
        {
            flag = 1;
            for (size_t i = 0; i < now.Path.size(); i++)
            {
                cout << now.Path[i];
                if (i != now.Path.size() - 1)
                {
                    cout << "-";
                }
            }
            return;
        }
        if (cnt[u] > k)
        {
            continue;
        }
        for (auto nxt : G[u])
        {
            vector<int> NP(now.Path); //not NP problem
            
            int v = nxt.first, c = nxt.second;
            NP.push_back(v);
            Q.push(Node(v, g + c, NP));
        }
    }
}

int main()
{
    cin >> n >> m >> k >> s >> t;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(make_pair(v, w));
        RG[v].push_back(make_pair(u, w));
    }
    Rdijkstra();
    AS(); //not ass
    if (!flag)
    {
        cout << "No";
    }
    return 0;
}

only T1 T2 AC
甚至T2的答案是No
样例都没过
贴一下原题 P4467 [SCOI2007] k短路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1 个赞
4

关键就在于如何保证as跑出来的路径是简单路径

5

但k短路的正解是可持续化可并堆（doge

7

不会， 但给你解决方案