OIer - FankerWang

一个不正经的信息学博客

Luogu P3946 ことりのおやつ(小鸟的点心)

《Luogu P3946 ことりのおやつ(小鸟的点心)》
难度:提高+/省选-
先来说一下思路:

  • 很容易看出来这是单源最短路的送分(ming)题,移动速度恒为1m/s,所以我们可以把所有时间转化为距离考虑。

  • 注意到题目中给出的“如果到达这个地点的时候,这里的雪的高度高于li则会被困在这个点走不出去”,推理得到第 i 个点雪高度高到不能通过的经历时间为 t = ( hi – li ) / q ,转化为能通过点 i 的条件:到达点 i 时已经走过的最大路程为t。

  • 然后你RE了40分的点,发现存在不下雪(q=0)的情况,于是加上对q=0的特判。

  • 题目中还给出“ことり想在g秒内回到家吃点心,越快越好”,也就是说如果松弛操作时选择走某条路后的总路程大于g,就不需要对这条边进行松弛操作了,因为走这条边肯定得不到正解。

  • SPFA一遍后察看目标点距离是否被更新,如果被更新过,更新过的值就是答案。如果没被更新过,说明无法到达终点,输出无解即可。

  • 然后你WA了#19,发现不需要考虑终点会不会雪太厚被困住(把我困在家里吧我不想上学(┬_┬))。

  • 修改终点限制为无穷大,AC了。

  • 优化思路:邻接表存边用list的好少,主要是STL很慢…不过这道题还是能过的,list看起来也更优雅对吧…如果用堆优化Dijkstra,但是由于能(wo)过(lan),所以就没用,想看Dijkstra解法的看标程吧。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<list>
#include<climits>
using namespace std;
const int MAXN = 100000 + 100;
int lim[MAXN]; //到达每个节点时最大允许已经走过的路程
int dis[MAXN]; //存储源点到每个点的最小距离
int n, m, s, t, g, q;
bool inP[MAXN]; //SPFA中用到,是否在集合P中
struct edge{ int to, length; };
list<edge> edges[MAXN];
void addedge( int u, int v, int w ){ edges[u].push_back( (edge){ v,w } ); }
void spfa(){
    //初始化dis为无穷大
    for( int i=1; i<=n; i++ ) dis[i] = INT_MAX; 
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    inP[s] = true;
    while( !q.empty() ){
        int cur = q.front(); q.pop();
        inP[cur] = false;
        //松弛操作,遍历cur的每条出边
        for( list<edge>::iterator it = edges[cur].begin(); it != edges[cur].end(); it++ )
            //判断松弛操作能否进行的特殊条件
            if( dis[cur] + it->length <= lim[it->to] && dis[cur] + it->length < g )
                //确认可以访问下一个节点,尝试进行松弛操作 
                if( dis[cur] + it->length < dis[it->to] ){
                    dis[it->to] = dis[cur] + it->length;
                    if( !inP[it->to] ) q.push( it->to ) , inP[it->to] = true;
                }
    }
}
int main(){
    scanf( "%d %d %d %d %d %d", &n, &m, &s, &t, &g, &q );
    for( int i=1; i<=n; i++ ){
        int li, hi; scanf( "%d %d", &hi, &li );
        //注意q可能为零,要特判,不然会RE的!
        if( q == 0 ){ lim[i] = li - hi; continue; }
        lim[i] = ( li - hi ) / q;
    } 
    //把终点的雪忽略掉
    lim[t] = INT_MAX; 
    for( int i=1; i<=m; i++ ){
        int tu, tv, tw; scanf( "%d %d %d", &tu, &tv, &tw );
        addedge( tu, tv, tw );
        addedge( tv, tu, tw );
    }
    spfa();
    if( dis[t] == INT_MAX ) //到不了家 
        printf( "wtnap wa kotori no oyatsu desu!\n" );
     else
         printf( "%d\n", dis[t] );
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注