ACM-ICPC 2018 沈阳赛区网络预赛 D. Made In Heaven（第k短路模板）

求第k短路模板

先逆向求每个点到终点的距离，再用dij算法，不会超时（虽然还没搞明白为啥。。。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

#include<fstream>

#include<cstdlib>

#include<ctime>

#include<list>

#include<climits>

#include<bitset>

#include<random>

#include <ctime>

#include <cassert>

#include <complex>

#include <cstring>

#include <chrono>

using namespace std;

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("input.in", "r", stdin);freopen("output.in", "w", stdout);

#define left asfdasdasdfasdfsdfasfsdfasfdas1

#define tan asfdasdasdfasdfasfdfasfsdfasfdas

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

typedef unsigned int un;

const int desll[][]={{,},{,-},{,},{-,}};

const int mod=1e9+;

const int maxn=1e3+;

const int maxm=1e5+;

const double eps=1e-;

int n,k,m;

int ar[maxn];

int head[maxn],sz,rehead[maxn];

bool vis[maxn];

int dis[maxn];

struct node

{

    int b,nex,c;

}no[maxn*],reno[maxn*];

void add(int a,int b,int c)

{

    no[sz].b=b;

    no[sz].c=c;

    no[sz].nex=head[a];

    head[a]=sz;

    reno[sz].b=a;

    reno[sz].c=c;

    reno[sz].nex=rehead[b];

    rehead[b]=sz++;

}

struct state{

    int all,pre,v;

    state(int a,int b,int c){

        all=a;pre=b;v=c;

    }

    state(){

    }

    bool operator<(const state& s)const{

        return all>s.all;

    }

};

priority_queue<state> qu;

void init(int s,int e)

{

    memset(vis,,sizeof(vis));

    memset(dis,-,sizeof(dis));

    queue<int> qu;

    qu.push(e);vis[e]=;

    dis[e]=;

    while(qu.size()){

        int x=qu.front();

        qu.pop();

        vis[x]=;

        for(int i=rehead[x];i!=-;i=reno[i].nex){

            int v=reno[i].b;

            if(dis[v]==- || dis[v]>dis[x]+reno[i].c){

                dis[v]=dis[x]+reno[i].c;

                if(vis[v]==){

                    vis[v]=;

                    qu.push(v);

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF){

        int s,e,k,t;

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

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

        memset(rehead,-,sizeof(rehead));sz=;

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

            int a,b,c;scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

        }

        int ans=;

        init(s,e);

        //for(int i=1;i<=n;i++)cout<<dis[i]<<" ";cout<<endl;

        if(dis[s]==-)ans=-;

        else{

            while(qu.size())qu.pop();

            qu.push(state(dis[s],,s));

            state mid;

            int ins=;

            while(qu.size()){

                mid = qu.top();

                qu.pop();

                if(mid.v==e){

                    ins++;

                    if(ins==k){

                        ans=mid.all;

                        break;

                    }

                }

                for(int i=head[mid.v];i!=-;i=no[i].nex){

                    int v=no[i].b;

                    qu.push(state(mid.pre+no[i].c+dis[v],mid.pre+no[i].c,v));

                }

            }

        }

        if(ans!=- && ans<=t)printf("yareyaredawa\n");

        else printf("Whitesnake!\n");

    }

    return ;

}