ACM-ICPC 2018 沈阳赛区网络预赛 Made In Heaven（K短路）题解

思路：K短路裸题

代码：

#include<queue>

#include<cstring>

#include<set>

#include<map>

#include<stack>

#include<string>

#include<cmath>

#include<vector>

#include<cstdio>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int maxm =  + ;

const int seed = ;

const ll MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

struct Edge{

    int v, w, next;

};

struct As{

    int f, g, pos;

    bool operator < (const As a) const{

        return a.f == f? a.g < g : a.f < f;

    }

};

int n, m, k, tot1, tot2, T;

int head1[maxn], head2[maxn], dis[maxn];

bool vis[maxn];

Edge edge1[maxm], edge2[maxm];

void init(){

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

    memset(head2, -, sizeof(head2));

    tot1 = tot2 = ;

}

void addEdge(int u, int v, int w){

    edge1[tot1].v = v;

    edge1[tot1].w = w;

    edge1[tot1].next = head1[u];

    head1[u] = tot1++;

    edge2[tot2].v = u;

    edge2[tot2].w = w;

    edge2[tot2].next = head2[v];

    head2[v] = tot2++;

}

void spfa(int st){

    for(int i = ; i <= n; i++) dis[i] = INF;

    memset(vis, false, sizeof(vis));

    vis[st] = true;

    dis[st] = ;

    queue<int> q;

    while(!q.empty()) q.pop();

    q.push(st);

    while(!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = head2[u]; i != -; i = edge2[i].next){

            int v = edge2[i].v;

            int w = edge2[i].w;

            if(dis[v] > dis[u] + w){

                dis[v] = dis[u] + w;

                if(!vis[v]){

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

    }

}

int Astar(int st, int end){

   int cnt = ;

   priority_queue<As> q;

   while(!q.empty()) q.pop();

   if(st == end) k++;

   if(dis[st] == INF) return -;

   As a, b;

   a.pos = st, a.g = , a.f = a.g + dis[st];

   q.push(a);

   while(!q.empty()){

        a = q.top();

        q.pop();

        if(a.f > T) return -;

        if(a.pos == end && a.f <= T){

            cnt++;

            if(cnt == k) return ;

        }

        for(int i = head1[a.pos]; i != -; i = edge1[i].next){

            b.pos = edge1[i].v;

            b.g = a.g + edge1[i].w;

            b.f = b.g + dis[b.pos];

            q.push(b);

        }

   }

   return -;

}

int main(){

    int s, e;

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

        init();

        scanf("%d%d%d%d", &s, &e, &k, &T);

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

            int u, v, w;

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

            addEdge(u, v, w);

        }

        spfa(e);

        int ans = Astar(s, e);

        if(ans == -)

            printf("Whitesnake!\n");

        else

            printf("yareyaredawa\n");

    }

    return ;

}