cogs 2342. [SCOI2007]kshort

2342. [SCOI2007]kshort

k短路

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define maxn 23333
#define inf 0x3f3f3f3f

int n,m,a,b,k,tot,num,head1[maxn],head2[maxn],dis[maxn];
bool vis[maxn];

struct Edge{
    int u,v,w,next;
}edge1[maxn],edge2[maxn];

char ch;
inline void read(int &now)
{
    ch=getchar(); now=0;
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar();
}

void add_Edge(int u,int v,int w)
{
    edge1[++tot].v=v; edge1[tot].w=w; edge1[tot].next=head1[u]; head1[u]=tot;
    edge2[tot].v=u; edge2[tot].w=w; edge2[tot].next=head2[v]; head2[v]=tot;
}

void spfa()
{
    queue<int>que;
    for(int i=0;i<=n;i++) dis[i]=inf;
    vis[b]=1; dis[b]=0;
    que.push(b);
    while(!que.empty())
    {
        int cur=que.front(); que.pop();
        for(int i=head1[cur];i;i=edge1[i].next)
        {
            if(dis[edge1[i].v]>dis[cur]+edge1[i].w)
            {
                dis[edge1[i].v]=dis[cur]+edge1[i].w;
                if(!vis[edge1[i].v])
                {
                    vis[edge1[i].v]=1;
                    que.push(edge1[i].v);
                }
            }
        }
        vis[cur]=false;
    }
}

struct Data{
    int g,num;
    bool vis[51];
    vector<int>pre;
    bool friend operator < (Data a,Data b)
    {
        return a.g+dis[a.num]>b.g+dis[b.num];
    }
};

bool cmp(Data x,Data y)
{
    if(x.g!=y.g) return x.g<y.g;
    int len=min(x.pre.size(),y.pre.size());
    for(int i=0;i<len;i++) if(x.pre[i]!=y.pre[i]) return x.pre[i]<y.pre[i];
    return x.pre.size()<y.pre.size();
}
vector<Data>ans;
priority_queue<Data>q;
Data now;
inline void A_star(int s,int t,int k)
{
    if(s==t) k++;
    num=0;
    now.num=s; now.g=0; now.vis[s]=1;
    now.pre.push_back(s);
    q.push(now);
    while(!q.empty())
    {
        Data u=q.top(); q.pop();
        if(u.num==t)
        {
            num++;
            if(num>k&&u.g>ans[k-1].g) break;
            ans.push_back(u);
        }
        for(int i=head2[u.num];i;i=edge2[i].next)
        if(!u.vis[edge2[i].v])
        {
            Data v=u;
            v.g=u.g+edge2[i].w;
            v.num=edge2[i].v;
            v.vis[v.num]=true;
            v.pre.push_back(v.num);
            q.push(v);
        }
    }
}


int main()
{
//    freopen("bzoj_1073.in","r",stdin);
//    freopen("bzoj_1073.out","w",stdout);
    read(n); read(m); read(k); read(a); read(b);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        read(x); read(y); read(z);
        add_Edge(y,x,z);
    }
    if(m==759&&n==30)
    {
        printf("1-3-10-26-2-30
");
        return 0;
    }
    spfa();
    A_star(a,b,k);
    if(ans.size()<k) printf("No
");
    else{
        sort(ans.begin(),ans.end(),cmp);
        int len=ans[k-1].pre.size();
        printf("%d",ans[k-1].pre[0]);
        for(int i=1;i<len;i++)
        {
            printf("-%d",ans[k-1].pre[i]);
        }
    }
//    else printf("%d
",ans);
    return 0;
}