文章摘要

LIK.CC-GPT

题目![acwing178. 第K短路](https://baicai777.cn/upload/2022/08/image-1659517912141.png题解表示看了别人的题解还是没有怎么会。#include<iostream>#include<cstring>#inc

题目

题解

表示看了别人的题解还是没有怎么会。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
typedef pair<int,PII>PIII;

const int N=1010,M=200010;
int dist[N],cnt[N];
int h[N],rh[N],w[M],ne[M],e[M],idx;
int S,T,K, n,m;

bool st[N];
void add(int h[],int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dijkstra(){
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,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;
        for(int i=rh[ver];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>w[i]+dist[ver]){
                dist[j]=w[i]+dist[ver];
                heap.push({dist[j],j});
            }
        }
    }
}
int A_star(){
    priority_queue<PIII,vector<PIII>,greater<PIII>>heap;
    heap.push({dist[S],{0,S}});
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int ver=t.y.y,distence=t.y.x;
        cnt[ver]++;
        if(cnt[T]==K)return distence;
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(cnt[j]<K){
                heap.push({distence+w[i]+dist[j],{distence+w[i],j}});
            }
        }
    }
    return -1;
}
int main(){
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);
    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    cin>>S>>T>>K;
    if(S==T)K++;
    dijkstra();
    
    cout<<A_star()<<endl;
    return 0;
}