poj 2449 k短路+A*算法

K短路的定义：

1.如果起点终点相同，那么0并不是最短路，而是要出去一圈回来之后才是最短路，那么第K短路也是一样。

2.每个顶点和每条边都可以使用多次。（可以存在环和来回走）

给定起终点，求K短路的长度

然后求K短路使用A*算法，其估价函数f(n) = g(n)+h(n)，h(n)是终点到结点n的最短路径，g(n)是起点到结点n的实际代价，这样选择显然能满足A*估价函数的要求，g(n)>=g'(n)，

h(n)<=h'(n)。

h(n)可以对原图的逆图进行SPFA得出。

终止条件是，如果终点第K次出队的话，那么表明已经找到第K短路。

注意处理起点终点不连通的情况。

#pragma comment(linker, "/STACK:36777216")

#pragma GCC optimize ("O2")

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

#define clr1(x) memset(x,-1,sizeof(x))

#define eps 1e-9

const double pi = acos(-1.0);

typedef long long LL;

typedef unsigned long long ULL;

const int modo = 1e9 + 7;

const int INF = 0x3f3f3f3f;

const int inf = 0x3fffffff;

const int maxn = 1005,maxm = 100005;

struct edge{

    int v,w,next;

    edge(){};

    edge(int vv,int ww,int nnext):v(vv),w(ww),next(nnext){};

}e[maxm<<1];

struct node{

    int f,g,v;

    node(){};

    node(int ff,int gg,int vv):f(ff),g(gg),v(vv){};

    bool operator < (const node &a) const{

        return a.f < f;

    }

};

int head[maxn],tail[maxn],dist[maxn],inq[maxn];

int n,m,s,t,k,ecnt;

void init()

{

    clr1(head),clr1(tail);

    ecnt = 0;

    fill(dist,dist+maxn,inf);

    clr0(inq);

}

void add(int u,int v,int w)

{

    e[ecnt] = edge(v,w,head[u]);

    head[u] = ecnt++;

    e[ecnt] = edge(u,w,tail[v]);

    tail[v] = ecnt++;

}

void spfa(int src)

{

    queue<int> q;

    q.push(src);dist[src] = 0,inq[src] = 1;

    while(!q.empty()){

        int cur = q.front();

        q.pop();inq[cur] = 0;

        for(int i = tail[cur];i != -1;i = e[i].next){

            int nxt = e[i].v;

            if(dist[nxt] > dist[cur] + e[i].w){

                dist[nxt] = dist[cur] + e[i].w;

                if(!inq[nxt])

                    inq[nxt] = 1,q.push(nxt);

            }

        }

    }

}

int Astar(int src,int dst){

    priority_queue<node> q;

    if(dist[src] == inf)

        return -1;

    clr0(inq);

    q.push(node(dist[src],0,src));

    while(!q.empty()){

        node cur = q.top();

        q.pop();

        inq[cur.v]++;

        if(inq[dst] == k)

            return cur.f;

        if(inq[cur.v] > k)

            continue;

        for(int i = head[cur.v];i != -1;i = e[i].next){

            node nxt(dist[e[i].v] + e[i].w + cur.g,e[i].w + cur.g,e[i].v);

            q.push(nxt);

        }

    }

    return -1;

}

int main(){

    int u,v,w;

    while(~RD2(n,m)){

        init();

        while(m--){

            RD3(u,v,w);u--,v--;

            add(u,v,w);

        }

        RD3(s,t,k);s--,t--;

        spfa(t);

        if(s == t)//如果起点终点相同，0不是第1短路径。。

            k++;

        printf("%d\n",Astar(s,t));

    }

    return 0;

}

秒客网

poj 2449 k短路+A*算法

相关文章