求第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[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; const int mod=1e9+7; const int maxn=1e3+7; const int maxm=1e5+7; const double eps=1e-8; 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*10],reno[maxn*10]; 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,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); queue<int> qu; qu.push(e);vis[e]=1; dis[e]=0; while(qu.size()){ int x=qu.front(); qu.pop(); vis[x]=0; for(int i=rehead[x];i!=-1;i=reno[i].nex){ int v=reno[i].b; if(dis[v]==-1 || dis[v]>dis[x]+reno[i].c){ dis[v]=dis[x]+reno[i].c; if(vis[v]==0){ vis[v]=1; 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,-1,sizeof(head)); memset(rehead,-1,sizeof(rehead));sz=0; for(int i=0;i<m;i++){ int a,b,c;scanf("%d%d%d",&a,&b,&c); add(a,b,c); } int ans=0; init(s,e); //for(int i=1;i<=n;i++)cout<<dis[i]<<" ";cout<<endl; if(dis[s]==-1)ans=-1; else{ while(qu.size())qu.pop(); qu.push(state(dis[s],0,s)); state mid; int ins=0; 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!=-1;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!=-1 && ans<=t)printf("yareyaredawa "); else printf("Whitesnake! "); } return 0; }