把路障看成智障的我,笑了5s 然后默然 (MDZZ)qwq

昨天开到一个关于次短路和k短路的帖子,就拿A* 去水了一下次短路,结果luoguAC,LOJWA , 。。。。你谷数据太水,都没照着题意写造一个最短路有多条的情况 ~~~

题目 : Luogu

首先题目 哇一个裸的$k$短路 qwq (NOIP 只会背板子选手,如果您会最短路求次短路…..qwq)

s

不过这题必须要 严格k短路 ,也就是第k-1短路可能有多条(不过数据水啊,不严格也行,要不是我在LOJ上面WA了,我都不知道要严格 qwq

s

由于不会 k 短路的正解,只能靠着A* 水水 qwq

如果您不会A* 百度,google上自学吧 qwq 或者您可以去 K短路的板子那里学学(不过那题A$*$被卡了 qwq)

先上一个 A* 求 k短路 的过程

算法过程:

  1. 将图反向,用Dijstra+heap求出t到所有点的最短距离,目的是求所有点到点t的最短路,用dis[i]表示i到t的最短路,其实这就是$A*$的启发函数,显然:$h(n)
  2. 定义估价函数。我们定义$g(n)$为从s到n所花费的代价,$h(n$)为$dis[n]$,显然这符合$A*$算法的要求。

  3. 初始化状态。状态中存放当前到达的点$i,f_i,g_i$。显然,$f_i=g_i+dis[i]$。初始状态为$(S,dis[S],0)$,存入优先级队列中。

  4. 状态转移。假设当前状态所在的点v相邻的点u,我们可以得到转换:$(V,fv,gv)$–>$(U,fu+w[v][u],gv+w[v][u])$。

  5. 终止条件。每个节点最多入队列$K$次,当$t$出队列$K$次时,即找到解。


int n,m;

struct e{
    int u,v,val;  
}edge[maxn],edge_hx[maxn];//edge_hx表示 求解的正向边 , edge[]求Dijkstra的反向最短路

int head[maxn],tot,head_hx[maxn],toth;
void add(int u,int v,int val){
    edge[++tot].v = v;
    edge[tot].u = head[u];
    head[u] = tot;
    edge[tot].val = val;

    edge_hx[++toth].v = v;//这题边是双向的所以建反边等于没说
    edge_hx[toth].u = head_hx[u];
    head_hx[u] = toth;
    edge_hx[toth].val = val;

}
struct node{
    int num,dis;
    bool operator < (const node &ano) const{
        return dis==ano.dis ? num > ano.num : dis > ano.dis;
    }//Dijkstra 堆
};

priority_queue<node> q;//用于Dijkstra

int dis[maxn];

void Dijkstra(int ed){
    //就一个最短路
}
struct Node
{
    int x,val;
    bool operator< (const Node &a)const{
        return val+dis[x] > a.val+dis[a.x];
    }//用于计算优先队列 , 估价函数 由于优先队列默认从大到小,所以重载也要反着来
};

priority_queue<Node>Q;//用于A*

int cnt[maxn];//计算次数

int Astar(int st, int ed, int k){

    Q.push( (Node){ st, 0} );
    while( !Q.empty() ){

        Node u= Q.top(); Q.pop();

        ++cnt[u.x];

        if(cnt[u.x] == k && u.x == ed) return u.val;//如果出现次数为k,且为重点的话,返回第k短路的值
        if(cnt[u.x] > k) continue;

        for(int i=head_hx[u.x];i;i=edge_hx[i].u){
            int v= edge_hx[i].v, w= edge_hx[i].val;
            Q.push((Node){v, u.val + w});//将每个状态加入优先队列
        }
    }
    return -1;
}

int main()
{
    n = read(),m=read();
    fors(i,1,m){
        int u = read(),v = read() , w = read();
        add(u,v,w);
        add(v,u,w);

    }
    int st=1, ed=n, k=2;//这里求第二短路
    if( st==ed ) ++k;
    Dijkstra(ed);

    writen(Astar( st, ed, k ));
    return 0;
}

你谷这题数据太水,上面的代码就可以AC(70ms)

接着我们考虑 严格k短路 严格次短路我们就去掉重复的值(set!!)

使用set去重 !!!每次当到达终点的时候就将值加入set,判断set的size == k就可以了,给出完整代码 qwq(你也可以使用其他的一些东东 代替set)

const int  maxn =  2e5+7;
const int int_max = (1ll<<31)-1;
#define int_min = -int_max - 1;
const int mod = 1e8;

int n,m;

struct e{
    int u,v,val;  
}edge[maxn],edge_hx[maxn];

int head[maxn],tot,head_hx[maxn],toth;
void add(int u,int v,int val){
    edge[++tot].v = v;//如果不是双向边,一定要反向啊qwq
    edge[tot].u = head[u];
    head[u] = tot;
    edge[tot].val = val;

    edge_hx[++toth].v = v;
    edge_hx[toth].u = head_hx[u];
    head_hx[u] = toth;
    edge_hx[toth].val = val;

}
struct node{
    int num,dis;
    bool operator < (const node &ano) const{
        return dis==ano.dis ? num > ano.num : dis > ano.dis;
    }
};

priority_queue<node> q;

int dis[maxn];

void Dijkstra(int ed){
    memset(dis,127,sizeof dis);
    dis[ed]=0;

    q.push((node){ed,0});

    while(!q.empty()){
        node u=q.top();q.pop();

        if(u.dis != dis[u.num]) continue;

        for(int i=head[u.num];i;i=edge[i].u){
            int v=edge[i].v;
            if(dis[v] > u.dis+edge[i].val) 
                dis[v]=u.dis+edge[i].val,q.push((node){v,dis[v]});
        }
    }
}
struct Node
{
    int x,val;
    bool operator< (const Node &a)const{
        return val+dis[x] > a.val+dis[a.x];
    }
};

priority_queue<Node>Q;

set<int> dis_kth;

int Astar(int st, int ed, int k){

    Q.push( (Node){ st, 0} );
    while( !Q.empty() ){

        Node u= Q.top(); Q.pop();

        if(u.x == ed) dis_kth.insert(u.val);//如果到达终点就加到set
        if(k == dis_kth.size() && u.x == ed) return u.val;//大小相同并且是终点则直接返回这个值
        if(dis_kth.size() > k) continue;
        //如果大于 k 的话,就直接continue
        for(int i=head_hx[u.x];i;i=edge_hx[i].u){
            int v= edge_hx[i].v, w= edge_hx[i].val;
            Q.push((Node){v, u.val + w});
        }
    }
    return -1;
}

int main()
{
    n = read(),m=read();
    fors(i,1,m){
        int u = read(),v = read() , w = read();
        add(u,v,w);
        add(v,u,w);

    }
    int st=1, ed=n, k=2;//这里是k = 2短路
    if( st==ed ) ++k;//st ==  ed 默认存在一条最短的边
    Dijkstra(ed);
    writen(Astar( st, ed, k ));
    return 0;
}
分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。---2018 NOIP 退役人士

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *