题目链接:https://nanti.jisuanke.com/t/31445
题意是输入n和m表示n个点m条边,然后输入起始点和终止点和第k短路和一个限制条件T,然后输入m条边。问能不能在T时间内从起始点到达终止点。
做法就是裸的k短路,当返回值为-1和时间大于T的都要输出"Whitesnake!"...
AC代码:
#include <bits/stdc++.h>
#define maxn 1100
#define maxm 11000
#define inf 0xfffffff
#define ll long long
using namespace std;
struct Node{
int to,w,next;
}Edge[maxm],Edge1[maxm];
int head[maxn],head1[maxn];
struct node{
int to,g,f;
bool operator < (const node &a) const{
if(a.f == f){
return a.g < g;
}
return a.f < f;
}
};
int dist[maxn];
bool vis[maxn];
int n,m,s,t,k,T;
void init(){
memset(Edge,0,sizeof(Edge));
memset(Edge1,0,sizeof(Edge1));
memset(head,-1,sizeof(head));
memset(head1,-1,sizeof(head1));
}
void spfa(int s){
for(int i=0;i<=n;i++){
dist[i] = inf;
}
memset(vis,false,sizeof(vis));
vis[s] = 1;
dist[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i=head1[u];i!=-1;i=Edge1[i].next){
int ans = dist[u] + Edge1[i].w;
if(ans < dist[Edge1[i].to]){
dist[Edge1[i].to] = ans;
if(!vis[Edge1[i].to]){
vis[Edge1[i].to] = 1;
q.push(Edge1[i].to);
}
}
}
}
}
int A_Star(){
node e,ne;
int cnt = 0;
priority_queue<node> q;
if(s == t) k ++;
if(dist[s] == inf) return -1;
e.to = s;
e.g = 0;
e.f = e.g + dist[e.to];
q.push(e);
while(!q.empty()){
e = q.top();
q.pop();
if(e.to == t) cnt ++;
if(cnt == k) return e.g;
for(int i=head[e.to];i!=-1;i=Edge[i].next){
ne.to = Edge[i].to;
ne.g = e.g + Edge[i].w;
ne.f = ne.g + dist[ne.to];
q.push(ne);
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
scanf("%d%d%d%d",&s,&t,&k,&T);
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
Edge[i].to = v;
Edge[i].w = w;
Edge[i].next = head[u];
head[u] = i;
Edge1[i].to = u;
Edge1[i].w = w;
Edge1[i].next = head1[v];
head1[v] = i;
}
spfa(t);
int ans = A_Star();
if(ans == -1 || ans > T){
puts("Whitesnake!");
}
else{
puts("yareyaredawa");
}
}
return 0;
}