K短路算法

野性酷女 2023-07-03 10:47 47阅读 0赞

**A\*算法**  
第k短路，很明显就是第k次到达终点第最短路经。  
详情可参考： https://oi-wiki.org/graph/kth-path/  
例题:http://poj.org/problem?id=2449

#include"stdio.h"
    #include"string.h"
    #include"queue"
    #include"algorithm"
    using namespace std;
    #define INF 0x3f3f3f3f
    typedef long long ll;
    typedef pair<ll,int> PII;
    const int maxn = 1000 + 7;
    struct Edge{ ///正向边
        int to,next;
        ll weight;
    }edge[maxn * 100];
    struct Re_Edge{ ///反向边
        int to,next;
        ll weight;
    }re_edge[maxn * 100];
    
    int n,m,s,e,tot,k,head[maxn],re_head[maxn],tot2;
    bool vis[maxn];
    ll dist[maxn];
    
    void addEdge(int a,int b,ll c){ ///正向加边
        edge[++ tot].to = b; edge[tot].next = head[a];
        edge[tot].weight = c; head[a] = tot;
    }
    void add_Redge(int a,int b,ll c){ /// 反向加边
        re_edge[++ tot2].to = b; re_edge[tot2].next = re_head[a];
        re_edge[tot2].weight = c; re_head[a] = tot2;
    }
    struct Node{
        int to;
        ll cost;
        bool operator < (const Node &another) const {
            return cost + dist[to] > another.cost + dist[another.to];
        }
        Node(int a,ll c):to(a),cost(c) {}
    };
    void DijsKla(int a) ///反向求终点到各个点之间的距离
    {
        dist[a] = 0;
        priority_queue<PII,vector<PII>,greater<PII> >que;
        que.push(PII(0,a));
        while(!que.empty()){
            PII p = que.top();
            que.pop();
            if(vis[p.second]) continue;
            vis[p.second] = 1;
            ll num = p.first;
            for(int i = re_head[p.second]; i != 0; i = re_edge[i].next){
                if(!vis[re_edge[i].to] && dist[re_edge[i].to] > num + re_edge[i].weight){
                    dist[re_edge[i].to] = num + re_edge[i].weight;
                    que.push(PII(dist[re_edge[i].to],re_edge[i].to));
                }
            }
        }
    }
    
    ll bfs(int a){
        priority_queue<Node> Q;
        Q.push(Node(a,0));
        while(!Q.empty()){
            Node node = Q.top();
            Q.pop();
            if(node.to == e){
                k --; if(k == 0) return node.cost;
            }
            for(int i = head[node.to]; i; i = edge[i].next){
                Q.push(Node(edge[i].to,node.cost + edge[i].weight));
            }
        }
        return -1;
    }
    int main()
    {
        while(scanf("%d%d",&n,&m) != EOF){
            tot = tot2 = 0;
            memset(dist,INF,sizeof(dist));
            memset(vis,0,sizeof(vis));
            memset(head,0,sizeof(head));
            memset(re_head,0,sizeof(head));;
            for(int i = 0; i < m; i ++){
                int a,b;
                ll v;
                scanf("%d%d%lld",&a,&b,&v);
                addEdge(a,b,v);
                add_Redge(b,a,v);
            }
            scanf("%d%d%d",&s,&e,&k);
            DijsKla(e);
            if(dist[s] == INF){
                printf("-1\n"); continue;
            }
            if(s == e) k ++;
            ll ans = bfs(s);
            printf("%lld\n",ans);
        }
        return 0;
    }