helianthus-kduanlu

从 Trac 迁移的文章

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

原文章内容如下：

#include<bits/stdc++.h>
using namespace std;

#define maxn 20100
#define maxm 20010
#define inf 1000000000

int head[maxn],nxt[maxm],head1[maxn],next1[maxm],S,T,k,K,n,m,e;
int dis[maxn];
bool vis[maxn];

struct edge{
    int u,v,c;
}a[maxm];

struct dat{
    int v,c;
    friend bool operator < (const dat&a,const dat&b){
        return a.c+dis[a.v]>b.c+dis[b.v];
    }
};

void add(int u,int v,int c)
{
    a[e]=(edge){u,v,c};
    nxt[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<dat> q;
    q.push((dat){src,0});
    while(!q.empty()){
        dat pre=q.top();q.pop();
        vis[pre.v]=true;
        for(int i=head1[pre.v];i+1;i=next1[i]){
            if(dis[a[i].u]>dis[pre.v]+a[i].c){
                dis[a[i].u]=dis[pre.v]+a[i].c;
                q.push((dat){a[i].u,0});
            }
        }
        while(!q.empty()&&vis[q.top().v]) q.pop();
    }
}

int astar(int src)
{
    priority_queue<dat> q;
    q.push((dat){src,0}); k--;
    while(!q.empty()){
        dat pre=q.top();q.pop();
        if(pre.v==T){
            if(k) k--;
            else return pre.c;
        }
        for(int i=head[pre.v];i+1;i=nxt[i]){
            q.push((dat){a[i].v,pre.c+a[i].c});
        }
    }
    return -1;
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(head,-1,sizeof(head));
        memset(head1,-1,sizeof(head1));
        memset(nxt,-1,sizeof(nxt));
        memset(next1,-1,sizeof(next1));
        e=0;
        scanf("%d%d%d%d",&S,&T,&k,&K);
        for(int i=0;i<m;i++){
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            add(u,v,c);
        }
        dij(T);
        if(dis[S]==inf){
            puts("Whitesnake!");
            continue;
        }
        if(S==T) k++;
        int tmp=astar(S);
        if(tmp<=K&&tmp!=-1) puts("yareyaredawa");
        else puts("Whitesnake!");
    }
}

#include

using namespace std;

#define maxn 20100

#define maxm 20010

#define inf 1000000000

int head[maxn],nxt[maxm],head1[maxn],next1[maxm],S,T,k,K,n,m,e;

int dis[maxn];

bool vis[maxn];

struct edge{

int u,v,c;

}a[maxm];

struct dat{

int v,c;

friend bool operator < (const dat&a,const dat&b){

return a.c+dis[a.v]>b.c+dis[b.v];

}

};

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

{

a[e]=(edge){u,v,c};

nxt[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 q;

q.push((dat){src,0});

while(!q.empty()){

dat pre=q.top();q.pop();

vis[pre.v]=true;

for(int i=head1[pre.v];i+1;i=next1[i]){

if(dis[a[i].u]>dis[pre.v]+a[i].c){

dis[a[i].u]=dis[pre.v]+a[i].c;

q.push((dat){a[i].u,0});

}

}

while(!q.empty()&&vis[q.top().v]) q.pop();

}

}

int astar(int src)

{

priority_queue q;

q.push((dat){src,0}); k--;

while(!q.empty()){

dat pre=q.top();q.pop();

if(pre.v==T){

if(k) k--;

else return pre.c;

}

for(int i=head[pre.v];i+1;i=nxt[i]){

q.push((dat){a[i].v,pre.c+a[i].c});

}

}

return -1;

}

int main(){

while(~scanf("%d%d",&n,&m)){

memset(head,-1,sizeof(head));

memset(head1,-1,sizeof(head1));

memset(nxt,-1,sizeof(nxt));

memset(next1,-1,sizeof(next1));

e=0;

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

for(int i=0;i

int u,v,c;

scanf("%d%d%d",&u,&v,&c);

add(u,v,c);

}

dij(T);

if(dis[S]==inf){

puts("Whitesnake!");

continue;

}

if(S==T) k++;

int tmp=astar(S);

if(tmp<=K&&tmp!=-1) puts("yareyaredawa");

else puts("Whitesnake!");

}

}