2018-ACM-ICPC沈阳网络预赛D题-A*模板题

发表于 | 分类于 ， | 热度 ℃
字数统计: 1,998 | 阅读时长 ≈ 11

Made In Heaven

问答

  • 14.67%
  • 1000ms
  • 131072K

One day in the jail, F·F invites Jolyne Kujo (JOJO in brief) to play tennis with her. However, Pucci the father somehow knows it and wants to stop her. There are NN spots in the jail and MM roads connecting some of the spots. JOJO finds that Pucci knows the route of the former (K-1)(K−1)-th shortest path. If Pucci spots JOJO in one of these K-1K−1 routes, Pucci will use his stand Whitesnake and put the disk into JOJO’s body, which means JOJO won’t be able to make it to the destination. So, JOJO needs to take the KK-th quickest path to get to the destination. What’s more, JOJO only has TT units of time, so she needs to hurry.

JOJO starts from spot SS, and the destination is numbered EE. It is possible that JOJO’s path contains any spot more than one time. Please tell JOJO whether she can make arrive at the destination using no more than TT units of time.

Input

There are at most 5050 test cases.

The first line contains two integers NN and MM (1 \leq N \leq 1000, 0 \leq M \leq 10000)(1≤N≤1000,0≤M≤10000). Stations are numbered from 11 to NN.

The second line contains four numbers S, E, KS,E,K and TT ( 1 \leq S,E \leq N1≤S,E≤N, S \neq ES≠E, 1 \leq K \leq 100001≤K≤10000, 1 \leq T \leq 1000000001≤T≤100000000 ).

Then MM lines follows, each line containing three numbers U, VU,V and WW (1 \leq U,V \leq N, 1 \leq W \leq 1000)(1≤U,V≤N,1≤W≤1000) . It shows that there is a directed road from UU-th spot to VV-th spot with time WW.

It is guaranteed that for any two spots there will be only one directed road from spot AA to spot BB (1 \leq A,B \leq N, A \neq B)(1≤A,B≤N,A≠B), but it is possible that both directed road <A,B><A,B>and directed road <B,A><B,A> exist.

All the test cases are generated randomly.

Output

One line containing a sentence. If it is possible for JOJO to arrive at the destination in time, output "yareyaredawa" (without quote), else output "Whitesnake!" (without quote).

样例输入复制

1
2
3
4
2 2
1 2 2 14
1 2 5
2 1 4

样例输出复制

1
yareyaredawa

题目来源

ACM-ICPC 2018 沈阳赛区网络预赛

题意

N个点，M条边，起始点为s，结束为n，求s到n的第k短的路的长度，判断长度是否大于T，如果大于，输出“Whitesnake!”，否则输出“yareyaredawa”

类似POJ2449

题解

A*+SPFA

A*算法：

1
2
3
4
A*，启发式搜索，是一种较为有效的搜索方法。
我们在搜索的时候，很多时候在当前状态，已经不是最优解了，但是我们却继续求解；这个就是暴力搜索浪费时间的原因。
我们在有些时候，往往可以根据一些信息推断出继续搜索是一种劣解。
所以如果能够判断出来的话，就可以不继续了，以达到节省运行时间的目的。

估价函数：

1
2
3
4
5
6
7
8
为了提高搜索效率，我们可以对未来可能产生的代价进行预估。我们设计一个估价函数，以任意状态输入，计算出从该状态到目标状态所需代价的估计值。
在搜索时，我们总沿着当前代价+未来估价最小的状态进行搜索。

估价函数需要满足：
　　设当前状态state到目标函数所需代价的估计值为f(state)
　　设在未来的搜索中，实际求出的从当前状态state到目标状态的最小代价为g(state)
　　对于任意的state，应该有f(state)<=g(state)
也就是说，估价函数的估值不能大于未来实际代价，估价比实际代价更优。

第K短路：

1
2
3
4
5
6
7
8
根据估价函数的设计准则，在第K短路中从x到T的估计距离f(x)应该不大于第K短路中从x到T的实际距离g(x)，于是，我们可以把估价函数f(x)定为从x到T的最短路径长度，这样不但能保证f(x)<=g(x)，还能顺应g(x)的实际变化趋势。
实现过程：
1.预处理f(x)，在反向图上以T为起点求到每个点的最短路
2.定义堆，维护{p,g,h}，p是某一个点，g是估价，h是实际，那么g+h更小的点p会优先访问
3.取出堆顶元素u扩展，如果节点v被取出的次数尚未达到k，就把新的{v,g,h+length(u,v)}插入堆中
4.重复第2-3步，直到第K次取出终点T，此时走过的路径长度就是第K短路

因为估价函数的作用，图中很多节点访问次数远小于K

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
const ll maxn=100010;
ll n,m,dis[maxn];
ll tot,head1[maxn],head2[maxn];
bool flag[maxn];
struct edge
{
    ll to;
    ll w;
    ll next;
}e[maxn*2],e2[maxn*2];
struct node
{
    ll f;
    ll g;
    ll from;
    bool operator < (node a)const
    {
        if(a.f==f)
        return g>a.g;
        return f>a.f;
    }
};
void add_edge(ll u,ll v,ll w)
{
    tot++;
    e[tot].to=v;
    e[tot].w=w;
    e[tot].next=head1[u];
    head1[u]=tot;
    e2[tot].to=u;
    e2[tot].w=w;
    e2[tot].next=head2[v];
    head2[v]=tot;
}
void prepare()
{
    for(ll i=1;i<=n;i++)
    dis[i]=maxn;tot=0;
    memset(head1,0,sizeof(head1));
    memset(head2,0,sizeof(head2));
}
void spfa(ll t)
{
    for(ll i=1;i<=n;i++)
    dis[i]=maxn;
    dis[t]=0;
    queue<ll> q;
    q.push(t);
    flag[t]=1;
    while(!q.empty())
    {
        ll v=q.front();
        q.pop();flag[v]=0;
        for(ll i=head2[v];i;i=e2[i].next)
        if(dis[e2[i].to]>dis[v]+e2[i].w)
        {
            dis[e2[i].to]=dis[v]+e2[i].w;
            if(!flag[e2[i].to])
            {
                q.push(e2[i].to);
                flag[e2[i].to]=1;
            }
        }
    }
}
ll a_star(ll s,ll t,ll k)
{
    if(s==t) k++;
    if(dis[s]==maxn) return -1;
    priority_queue<node> q;
    ll cnt=0;
    node tmp,to;
    tmp.from=s;
    tmp.g=0;
    tmp.f=tmp.g+dis[tmp.from];
    q.push(tmp);
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        if(tmp.from==t) cnt++;
        if(cnt==k) return tmp.g;
        for(ll i=head1[tmp.from];i;i=e[i].next)
        {
            to.from=e[i].to;
            to.g=tmp.g+e[i].w;
            to.f=to.g+dis[to.from];
            q.push(to);
        }
    }
    return -1;
}
int main()
{
    ll x,y,z,s,t,k;
    ll T;
    while(cin>>n>>m)
    {
        cin>>s>>t>>k>>T;
        prepare();
        for(ll i=1;i<=m;i++)
        {
            cin>>x>>y>>z;
            add_edge(x,y,z);
        }
        spfa(t);
        ll ans=a_star(s,t,k);
        if(ans<=T&&ans!=-1)
            cout<<"yareyaredawa"<<endl;
        else
            cout<<"Whitesnake!"<<endl;
    }
    return 0;
}

k短路模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
const ll maxn=100010;
ll n,m,dis[maxn];
ll tot,head1[maxn],head2[maxn];
bool flag[maxn];
struct edge
{
    ll to;
    ll w;
    ll next;
}e[maxn*2],e2[maxn*2];
struct node
{
    ll f;
    ll g;
    ll from;
    bool operator < (node a)const
    {
        if(a.f==f)
        return g>a.g;
        return f>a.f;
    }
};
void add_edge(ll u,ll v,ll w)
{
    tot++;
    e[tot].to=v;
    e[tot].w=w;
    e[tot].next=head1[u];
    head1[u]=tot;
    e2[tot].to=u;
    e2[tot].w=w;
    e2[tot].next=head2[v];
    head2[v]=tot;
}
void prepare()
{
    for(ll i=1;i<=n;i++)
    dis[i]=maxn;tot=0;
    memset(head1,0,sizeof(head1));
    memset(head2,0,sizeof(head2));
}
void spfa(ll t)
{
    for(ll i=1;i<=n;i++)
    dis[i]=maxn;
    dis[t]=0;
    queue<ll> q;
    q.push(t);
    flag[t]=1;
    while(!q.empty())
    {
        ll v=q.front();
        q.pop();flag[v]=0;
        for(ll i=head2[v];i;i=e2[i].next)
        if(dis[e2[i].to]>dis[v]+e2[i].w)
        {
            dis[e2[i].to]=dis[v]+e2[i].w;
            if(!flag[e2[i].to])
            {
                q.push(e2[i].to);
                flag[e2[i].to]=1;
            }
        }
    }
}
ll a_star(ll s,ll t,ll k)
{
    if(s==t) k++;
    if(dis[s]==maxn) return -1;
    priority_queue<node> q;
    ll cnt=0;
    node tmp,to;
    tmp.from=s;
    tmp.g=0;
    tmp.f=tmp.g+dis[tmp.from];
    q.push(tmp);
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        if(tmp.from==t) cnt++;
        if(cnt==k) return tmp.g;
        for(ll i=head1[tmp.from];i;i=e[i].next)
        {
            to.from=e[i].to;
            to.g=tmp.g+e[i].w;
            to.f=to.g+dis[to.from];
            q.push(to);
        }
    }
    return -1;
}
文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！