2017-team2/kpath

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>

using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
#define next fuckyou
#define inf 1000000000
#define MAXN 1005
#define MAXM 100005
int head[MAXN],next[MAXM],head1[MAXN],next1[MAXM];
int dis[MAXN];
bool vis[MAXN];
int n,m,e,st,en,k;
struct note
{
    int u,v,c;
    note(){}
    note(int u,int v,int c):u(u),v(v),c(c){}
}p[MAXM];
struct POJ
{
    int v,c;
    POJ(){}
    POJ(int v,int c):v(v),c(c){}
    bool operator <(const POJ& other)const
    {
        return c+dis[v]>other.c+dis[other.v];
    }
};
void addnote(int u,int v,int c)
{
    p[e]=note(u,v,c);
    next[e]=head[u]; head[u]=e;
    next1[e]=head1[v];head1[v]=e++;
}
void dij(int src)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[src]=0;
    priority_queue<POJ>que;
    que.push(POJ(src,0));
    while (!que.empty())
    {
        POJ pre=que.top(); que.pop();
        vis[pre.v]=true;
        for(int i=head1[pre.v];i+1;i=next1[i])
        {
            if (dis[p[i].u]>dis[pre.v]+p[i].c)
            {
                dis[p[i].u]=dis[pre.v]+p[i].c;
                que.push(POJ(p[i].u,0));
            }
        }
        while (!que.empty()&& vis[que.top().v])que.pop();
    }
}
int limit;
int a_star(int src)
{
    priority_queue<POJ> que;
    que.push(POJ(src,0)); k--;
    while (!que.empty())
    {
        POJ pre=que.top(); que.pop();
        if(pre.c>limit)return -1;
        if (pre.v==en)
        {
            if (k)k--;
            else return pre.c;
        }
        for(int i=head[pre.v];i+1;i=next[i])
            que.push(POJ(p[i].v,pre.c+p[i].c));
    }
    return -1;
}
int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(head,-1,sizeof(head));
        memset(head1,-1,sizeof(head1));
        e=0;
        scanf("%d%d%d%d",&st,&en,&k,&limit);
        for(int i=0;i<m;i++)
        {
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            addnote(u,v,c);
        }
        dij(en);
        if (dis[st]==inf){ puts("Whitesnake!"); continue; }
        if (st==en)k++;
        int shit=a_star(st);
        if (shit==-1 || shit>limit)puts("Whitesnake!"); else puts("yareyaredawa");
    }
    return 0;
}
}}}

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
#define next fuckyou
#define inf 1000000000
#define MAXN 1005
#define MAXM 100005
int head[MAXN],next[MAXM],head1[MAXN],next1[MAXM];
int dis[MAXN];
bool vis[MAXN];
int n,m,e,st,en,k;
struct note
{
    int u,v,c;
    note(){}
    note(int u,int v,int c):u(u),v(v),c(c){}
}p[MAXM];
struct POJ
{
    int v,c;
    POJ(){}
    POJ(int v,int c):v(v),c(c){}
    bool operator <(const POJ& other)const
    {
        return c+dis[v]>other.c+dis[other.v];
    }
};
void addnote(int u,int v,int c)
{
    p[e]=note(u,v,c);
    next[e]=head[u]; head[u]=e;
    next1[e]=head1[v];head1[v]=e++;
}
void dij(int src)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[src]=0;
    priority_queue<POJ>que;
    que.push(POJ(src,0));
    while (!que.empty())
    {
        POJ pre=que.top(); que.pop();
        vis[pre.v]=true;
        for(int i=head1[pre.v];i+1;i=next1[i])
        {
            if (dis[p[i].u]>dis[pre.v]+p[i].c)
            {
                dis[p[i].u]=dis[pre.v]+p[i].c;
                que.push(POJ(p[i].u,0));
            }
        }
        while (!que.empty()&& vis[que.top().v])que.pop();
    }
}
int limit;
int a_star(int src)
{
    priority_queue<POJ> que;
    que.push(POJ(src,0)); k--;
    while (!que.empty())
    {
        POJ pre=que.top(); que.pop();
        if(pre.c>limit)return -1;
        if (pre.v==en)
        {
            if (k)k--;
            else return pre.c;
        }
        for(int i=head[pre.v];i+1;i=next[i])
            que.push(POJ(p[i].v,pre.c+p[i].c));
    }
    return -1;
}
int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(head,-1,sizeof(head));
        memset(head1,-1,sizeof(head1));
        e=0;
        scanf("%d%d%d%d",&st,&en,&k,&limit);
        for(int i=0;i<m;i++)
        {
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            addnote(u,v,c);
        }
        dij(en);
        if (dis[st]==inf){ puts("Whitesnake!"); continue; }
        if (st==en)k++;
        int shit=a_star(st);
        if (shit==-1 || shit>limit)puts("Whitesnake!"); else puts("yareyaredawa");
    }
    return 0;
}