【BZOJ】1598: [Usaco2008 Mar]牛跑步

【题意】给定有向图，边严格从大编号指向小编号，求前k短路。n<=1000,m<=10000,k<=100。

【算法】归并+拓扑排序||A*求第k短路

【题解】因为此题自带拓扑序的特殊性，可以用归并写。

f[i][j]表示从i出发的第j短路，将i出去的点的前k短路依次归并。

复杂度O(m*k)。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cctype>

using namespace std;

const int maxn=,maxk=;

struct edge{int v,from,w;}e[];

int g[maxn][maxk],n,m,k,tot,first[maxn],b[maxn],c[maxn];

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}

void merge(int a[],int b[],int w){

    int l=,r=;

    for(int i=;i<=k;i++){

        if(a[l]<b[r]+w)c[i]=a[l++];else c[i]=b[r++]+w;

    }

    for(int i=;i<=k;i++)a[i]=c[i];

}

int main(){

    n=read();m=read();k=read();

    for(int i=;i<=m;i++){

        int u=read(),v=read(),w=read();

        insert(u,v,w);

    }

    memset(g,0x3f,sizeof(g));

    g[][]=;

    for(int x=;x<=n;x++){

        for(int i=first[x];i;i=e[i].from){

            merge(g[x],g[e[i].v],e[i].w);

        }

    }

    for(int i=;i<=k;i++)if(g[n][i]<0x3f3f3f3f)printf("%d\n",g[n][i]);else printf("-1\n");

    return ;

}

启发式搜索留坑：BZOJ 1598 牛跑步

大概做法是f(x)=h(x)+g(x)，其中h(x)是到终点估价。

这里采用从终点反跑最短路实现精确估价，然后根据A*的性质，第k次访问终点就是第k短路。