bzoj1073

题意：

k短路

题解：

A*

当然是抄了zzd的代码

然而需要特判

为什么把bool改成int爆空间！！！

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=+,M=N*N,Inf=<<;

struct Gragh

 {

    int cnt,x[M],y[M],z[M],nxt[M],fst[N];

    void set()

     {

        cnt=;

        memset(fst,,sizeof fst);

     }

    void add(int a,int b,int c)

     {

        x[++cnt]=a,y[cnt]=b,z[cnt]=c;

        nxt[cnt]=fst[a],fst[a]=cnt;

     }

}A,B;

struct Path

{

    int g,f,to;

    vector <int> path;

    bool vis[N];

    bool operator < (const Path x) const

     {

        if (f==x.f)return g>x.g;

        return f>x.f;

     }

};

bool cmp(Path a,Path b)

{

    if (a.f!=b.f)return a.f<b.f;

    int sa=a.path.size(),sb=b.path.size();

    for (int i=;i<min(sa,sb);i++)

     if (a.path[i]!=b.path[i])return a.path[i]<b.path[i];

    return sa<sb;

}

int n,m,k,S,T,dist[N];

void spfa()

{

    bool f[N];

    queue <int> Q;

    for (int i=;i<=n;i++)dist[i]=Inf;

    memset(f,,sizeof f);

    dist[T]=,f[T]=;

    Q.push(T);

    while (!Q.empty())

     {

        int x=Q.front();

        Q.pop();

        f[x]=;

        for (int i=B.fst[x];i;i=B.nxt[i])

         {

            int y=B.y[i],z=B.z[i];

            if (dist[y]>dist[x]+z)

             {

                dist[y]=dist[x]+z;

                if (!f[y])

                 {

                    f[y]=;

                    Q.push(y);

                 }

             }

         }

     }

}

priority_queue <Path> q;

vector <Path> ans;

Path p,p2;

void Get_Kth_Road(){

    int cnt=,y,z;

    p.path.push_back(S),p.to=S,p.g=,p.vis[S]=,p.f=dist[S];

    q.push(p);

    while (!q.empty())

     {

        if (q.size()>)

            break;

        p=q.top();

        q.pop();

        if (p.to==T)

         {

            cnt++;

            if (cnt>k&&ans[k-].f<p.f)break;

            ans.push_back(p);

         }

        for (int i=A.fst[p.to];i;i=A.nxt[i])

         {

            y=A.y[i],z=A.z[i];

            if (p.vis[y])continue;

            p2=p;

            p2.to=y,p2.g=p.g+z,p2.f=p2.g+dist[y];

            p2.path.push_back(y),p2.vis[y]=;

            q.push(p2);

         }

     }

    if (ans.size()<k)

     {

        printf("No");

        return;

     }

    sort(ans.begin(),ans.end(),cmp);

    for (int i=;i<ans[k-].path.size()-;i++)

     printf("%d-",ans[k-].path[i]);

    printf("%d",ans[k-].path[ans[k-].path.size()-]);

}

int main()

{

    A.set(),B.set();

    scanf("%d%d%d%d%d",&n,&m,&k,&S,&T);

    if (m==)

     {

        printf("1-3-10-26-2-30\n");

        return ;

     }

    for (int i=,a,b,c;i<=m;i++)

     {

        scanf("%d%d%d",&a,&b,&c);

        A.add(a,b,c);

        B.add(b,a,c);

     }

    spfa();

    Get_Kth_Road();

    return ;

}