? Acwing 178 && POJ 2449 ?

2022-09-18 12:59:16

写在前面

学习算法的日子又到了~~

Idea?

提供以下几种方法

暴搜
输出-1(是的，输出-1)
有算法的暴力
- \(Dijkstra\)
  - \(Dijkstra\)的本质是贪心，复杂度为\(O(n^2)\)，堆优化后为\(O((m+n) \log (m+n))\)
- \(SPFA\)
  - 学长说最好不要用，因为它死了
\(A^\ast\)
- \(y\)总有视频讲解，不懂的同学可以去看看，这里我就不再赘述了

下面直接进行\(A^\ast\)的讲解

所以，发现想出\(f\)很关键，,\(f\)要尽量大但不超过最优解

第几次出队就是第几短,于是终点出了\(k\)次就是第\(k\)短路了

按照\(Dijkstra\)的思想,我们每次取出\(d[x]+f[x]\) 最小的

然后更新所有能到达的点

发现\(f[x]\) 可以取到终点的距离,这样尽量大且一定比现在的解小

于是先倒着\(Dijkstra\)一遍(搞出\(f\))

然后\(A^ \ast\),直到终点第\(k\)次。

\(OK\),上代码

Code?

Code1

//Dijstra 暴力版
const int maxx=1001;
struct Node{
    int v,to,next;
}e[maxn<<1];
int head[maxx],dis[maxx];
int len,tot,n,m,v,S,T,K;
bool vis[maxn];
priority_queue<pair<int,int> >q;
inline void add(int x,int y,int z){
    e[++tot].v=y; e[tot].to=z;
    e[tot].next=head[x]; head[x]=tot;
}
inline bool dfs(int x){
    if(x==T) return true;
    vis[x]=true;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(!vis[y]) if(dfs(y)==true) 
            return true;
    }
    return false;
}
inline void dijkstra(){
    if(!dfs(S)){puts("-1");return;}
    q.push(make_pair(0,S));
    if(S==T) v=-1;
    while(q.size()){
        int d=q.top().first,x=q.top().second; q.pop();
        if(x==T){
            if(++v==K){printf("%d",-d);return;}
            len=0;
        }
        else if(++len==maxx*15)break;//防止搜过多 
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].v;
            q.push(make_pair(d-e[i].to,y));
        }
    }
    puts("-1");
}
signed main(){
    n=read(); m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);
    }
    S=read(); T=read(); K=read();
    dijkstra();
    return 0;
}

Code2

//Dijkstra + A*

const int maxx=1001;
struct Node{
    int y,to,next;
}e[maxn],e1[maxn];
int head[maxx],tot,head1[maxx],cnt;//head1为反向边 
int n,m,dis[maxx],S,T,K,vis[maxx];
inline void add(int x,int y,int z){
    e[++tot]=(Node){y,z,head[x]};
    head[x]=tot;
}
inline void add1(int x,int y,int z){//反边 
    e1[++cnt]=(Node){y,z,head1[x]};
    head1[x]=cnt;
}
priority_queue<pair<int,int> >q;//注意：这是大根堆 
inline void dijkstra(){
    mem(dis,0x3f); mem(vis,-1);
    dis[T]=0;
    q.push(make_pair(0,T));
    while(q.size()){
        int x=q.top().second;q.pop();
        if(!vis[x])continue; vis[x]=0;//每个点只贡献一次
        for(int i=head1[x];i;i=e1[i].next){
            int y=e1[i].y;
            if(dis[y]>dis[x]+e1[i].to){
                dis[y]=dis[x]+e1[i].to;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
}
inline void A_star(){
    if(dis[S]==dis[0]){puts("-1");return;}//不连通 
    if(S==T) K++;//路径必须有边吧。 
    mem(vis,0);
    q.push(make_pair(-dis[S],S));
    while(q.size()){
        int x=q.top().second,d=-q.top().first-dis[x];
        q.pop(); vis[x]++;
        if(vis[T]==K){printf("%d",d);return;}
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].y;
            if(vis[y]!=K)q.push(make_pair(-d-e[i].to-dis[y],y));
//重要剪枝——因为默认为大根堆并且每次取最小值，所以必须插入相反数或重载运算符。 
        }
    }
    puts("-1"); 
}
signed main(){
    n=read(); m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z); add1(y,x,z);
    }
    S=read(); T=read(); K=read();
    dijkstra();//跑反图，求出优秀的估价函数
    A_star(); 
    return 0;
}