ACM-ICPC 2018 沈阳赛区网络预赛 D Made In Heaven（第k短路，A*算法）

https://nanti.jisuanke.com/t/31445

题意

能否在t时间内把第k短路走完。

分析

A*算法板子。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
//const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 1e9;
const int maxn = 1000 + 10;
const int maxm = 100000 + 10;
const int mod = 1000000007;
int head[maxn],nxt[maxm],head1[maxn],nxt1[maxm];
int dis[maxn];
bool vis[maxn];
int n,m,e,st,en,k,t;
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);
    nxt[e]=head[u];head[u]=e;
    nxt1[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=nxt1[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 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.v==en){
            if(k) k--;
            else return pre.c;
        }
        for(int i=head[pre.v];i+1;i=nxt[i])
            if(pre.c+p[i].c<=t)
                que.push(POJ(p[i].v,pre.c+p[i].c));
    }
    return -1;
}
int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    while(~scanf("%d%d",&n,&m)){
        scanf("%d%d%d%d",&st,&en,&k,&t);
        memset(head,-1,sizeof(head));
        memset(head1,-1,sizeof(head1));
        e=0;
        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 ans=a_star(st);
        if(ans==-1||ans>t){
            puts("Whitesnake!");
        }else{
            puts("yareyaredawa");
        }
//        printf("%d
",a_star(st));
    }
    return 0;
}