百度之星(题解)

简介: 百度之星(题解)

今天是六一节,小度去公园玩,公园一共 N 个景点,正巧看到朋友圈度度熊也在这个公园玩,于是他们约定好一块去景点 N。 小度当前所在景点编号为 T,从一个景点到附近的景点需要消耗的体力是 TE,而度度熊所在景点编号为 F ,移动消耗为 FE。 好朋友在一块,赶路都会开心很多,所以如果小度和度度熊一块移动(即在相同位置向相同方向移动),每一步他俩的总消耗将会减少 S。

求他俩到景点 N 时,所需要的总消耗最少是多少?

格式

输入格式:

第一行三个数值,TE,FE,S ,分别代表小度移动消耗值,度度熊移动消耗值,一起移动的消耗减少值。1≤TE,FE,S≤40000,S≤TE+FE1≤TE,FE,S≤40000,S≤TE+FE;

第二行四个数值,T,F,N,M ,分别代表小度出发点,度度熊出发点,目标节点,总路径数。1≤T,F,N,M≤40000;

接下来M 行,每行两个整数 X,Y,代表连通的两个景点。1≤X,Y≤N。

输出格式:

一个整数,即总消耗最小值。如果不能到达 N , 输出-1。

样例 1

输入:

4 4 3

1 2 8 8

1 4

2 3

3 4

4 7

2 5

5 6

6 8

7 8


输出:22

#include<bits/stdc++.h> 
using namespace std;
int te,fe,s;
int t,f,n,m;
const int maxn=40005;
vector<int> v[maxn];
int p1[maxn],p2[maxn],d[maxn];
void bfs(int start,int val[]){
    for(int i=1;i<=n;i++) val[i]=n+1;
    queue<int> Q;
    Q.push(start);
    val[start]=0;
    while(!Q.empty()){
        int cur=Q.front();
        Q.pop();
        for(int i=0;i<v[cur].size();i++){
            int d=v[cur][i];
            if(val[d]>val[cur]+1){
                Q.push(d);
                val[d]=val[cur]+1;
            }
        }
    }
}
int main( )
{
    scanf("%d %d %d",&te,&fe,&s);
    scanf("%d %d %d %d",&t,&f,&n,&m);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(t,p1); bfs(f,p2); bfs(n,d);
    if(p1[n]==n+1||p2[n]==n+1){
        printf("-1");
    }else{
        int res=p1[n]*te+p2[n]*fe;
        for(int i=1;i<n;i++){
            int cur=p1[i]*te+p2[i]*fe+d[i]*(te+fe-s);
            res=min(res,cur);
        }
        printf("%d",res);
    }
    return 0;
}
相关文章
【 腾讯精选练习 50 题】10—爬楼梯【简单】
【 腾讯精选练习 50 题】10—爬楼梯【简单】
|
4月前
|
算法
力扣算题【第二期】
这是一个关于链表操作的算法总结,包括两个部分:1) 反转链表,通过头插法实现链表反转,代码中使用了迭代方式;2) 判断回文链表,利用快慢指针找到链表中点,翻转后半部分并与前半部分比较。代码中包含详细步骤及辅助的翻转函数。
26 0
|
4月前
华为23年9月笔试原题,巨详细题解,附有LeetCode测试链接
华为23年9月笔试原题,巨详细题解,附有LeetCode测试链接
【 腾讯精选练习 50 题】11—最大子序和【简单】
【 腾讯精选练习 50 题】11—最大子序和【简单】
|
机器学习/深度学习 安全
2023年百度之星题解
2023年百度之星题解
|
12月前
|
人工智能 BI
百度松果菁英班--oj赛(第一次)
百度松果菁英班--oj赛(第一次)
56 0
|
机器学习/深度学习
百度之星题解(蛋糕划分)
百度之星题解(蛋糕划分)
|
人工智能 物联网 BI
牛客月赛62思考和总结
牛牛在幼稚园做义工,幼稚园中共有 nnn 颗树,第 1 天中午时它们的高度分别为:h1,h2,…,hnh_1,h_2,…,h_nh1​,h2​,…,hn​ (单位:厘米)。每一天的晚上每棵树的高度都会增加 aaa 厘米,而牛牛的任务则是在第二天的清晨检查每一颗树的高度,若某颗树的高度超过了 kkk 厘米牛牛就会将它的高度修剪为 bbb 厘米。牛牛想请你帮它计算一下第 mmm 天中午每一颗树的高度。
107 0
|
人工智能 测试技术
2021年第十二届蓝桥杯模拟赛(第三期)题目和解析
蓝桥杯是指蓝桥杯全国软件和信息技术专业人才大赛。是由工业和信息化部人才交流中心举办的全国性IT学科赛事。共有北京大学、清华大学、上海交通大学等全国1200余所高校参赛。
351 0
2021年第十二届蓝桥杯模拟赛(第三期)题目和解析