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 = + ;
const int maxm = + ;
const int mod = ;
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,,sizeof(vis));
for(int i=;i<=n;i++) dis[i]=inf;
dis[src]=;
priority_queue<POJ> que;
que.push(POJ(src,));
while(!que.empty()){
POJ pre=que.top();que.pop();
vis[pre.v]=true;
for(int i=head1[pre.v];i+;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,));
}
}
while(!que.empty()&&vis[que.top().v]) que.pop();
}
}
int a_star(int src){
priority_queue<POJ> que;
que.push(POJ(src,));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+;i=nxt[i])
if(pre.c+p[i].c<=t)
que.push(POJ(p[i].v,pre.c+p[i].c));
}
return -;
}
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,-,sizeof(head));
memset(head1,-,sizeof(head1));
e=;
for(int i=;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==-||ans>t){
puts("Whitesnake!");
}else{
puts("yareyaredawa");
}
// printf("%d\n",a_star(st));
}
return ;
}
上一篇:【HTML5】video视频


下一篇:mac OS.NE开发环境搭建