正文

搜狗2019秋招的一道算法题：龟兔赛跑(代码片段)

面朝大海春暖花开  面朝大海春暖花开  2022-11-29  603

关键词：

时间限制：3秒

空间限制：92160K

定义如下图所示的比赛地图：
技术图片

S表示比赛起点，E表示比赛终点。实线表示陆路，虚线表示水路。兔子只能走陆路，乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟足够聪明，问谁先到达终点。

输入描述:

第1行输入v1，v2。v1是兔子的速度，v2是乌龟的速度（水路、陆路速度相同）。第2行输入n,m，点的编号是1~n,然后是m行，其中1是起点，n是终点（路径本身不限定方向）。下面m行4个数 a, b, d, c，表示a和b之间有一条边，且其长度为d，类型是c（0表示陆路，1表示水路）。最后一行是end，表示输入结束。输入保证1和n之间至少有一条路径联通。(1<n<=10000, 0<m<=1000000)。

输出描述:

输出-1,0,1中的一个数。-1表示乌龟获胜，1表示兔子获胜，0表示同时到达终点。

输入例子1:

输出例子1:

-1

声明：这道题在牛客提交只过了90%的数据，拿到了45分，最后一个样例没过，思考了很久，认为都考虑到了，又看了下分数排名，我认为他们的最后一个比较大的case数据有问题。如果有人都过了case
也可以留下评论，我哪里写错了。
代码如下：

#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#define INF 2100000000

using namespace std;

int n, m;
struct node

    int point; //端点
    int weight; //路径长度
    bool worl; //是否水路
;
vector<node>amap[10010];
unsigned int dis[10010];
bool vis[10010];

int Dijkstra(bool torr)

    memset(vis, false, sizeof(vis));
    for(int i=1; i<=n; i++) 
        dis[i] = INF; //代表不可达
    
    int len = amap[1].size();

    if(torr) 
        for(int i=0; i<len; i++) 
            if( amap[1][i].weight < dis[amap[1][i].point] )
                dis[amap[1][i].point] = amap[1][i].weight;
        
     else 
        for(int i=0; i<len; i++) 
            if( !amap[1][i].worl && amap[1][i].weight < dis[amap[1][i].point] )
                dis[amap[1][i].point] = amap[1][i].weight;
        
    

    vis[1] = true;

    for(int k=0; k<n-1; k++) 
        int pos, mdis = INF;

        for(int i=1; i<=n; i++) 
            if(!vis[i] && dis[i] < mdis) 
                mdis = dis[i]; pos = i;
            
        
        vis[pos] = true;
        len = amap[pos].size();

        if(torr == true)  // 乌龟的话，所有的dis都可以拿来更新
            for(int j=0; j<len; j++) 
                if( !vis[amap[pos][j].point] && dis[amap[pos][j].point] > (amap[pos][j].weight+dis[pos]) ) 
                    dis[ amap[pos][j].point ] = amap[pos][j].weight + dis[pos];
                
            
         else  // 兔子的话，更新的可选路径必须是陆路
            for(int j=0; j<len ; j++) 
                if( !vis[amap[pos][j].point] && !amap[pos][j].worl && dis[amap[pos][j].point] > (amap[pos][j].weight+dis[pos]) )
                    dis[ amap[pos][j].point ] = amap[pos][j].weight + dis[pos];
            
        
    
    return dis[n];


int main()

    double vt, vg;
    scanf("%lf %lf", &vt, &vg);
    scanf("%d %d", &n, &m);

    int a, b, c, d;
    node cur;
    for(int i=0; i<m; i++) 
        scanf("%d %d %d %d", &a, &b, &c, &d);
        cur.point = b;
        cur.weight = c;
        cur.worl = (d==1?true:false);
        amap[a].push_back(cur);
    
    char str[100];
    scanf("%s", str);

    double tt = (double)Dijkstra(false) / vt; // tu zi
    double tg = (double)Dijkstra(true) / vg; // gui

    double eps = 1e-8;
    if(fabs(tt - tg) < eps) 
        printf("0
");
     else if(tt - tg > eps) 
        printf("-1
");
     else 
        printf("1
");
    
    return 0;

算法是什么我记不住，butidoitmyway.解一道滴滴出行秋招编程题。

...自己，手贱。　　刷头条看到一篇文章写的滴滴出行2017秋招编程题，后来发现原文在这里http://www.cnblogs.com/SHERO-Vae/p/5882357.html。看了下，挺有意思，于是就想了想，又写了写，最终撸出来了。刚开始一看顿时感觉很熟悉，大学数... 查看详情

1.虎牙直播2019秋招编程题(代码片段)

第一题： #include<iostream>#include<string>usingnamespacestd;boolIsVoChar(charc)return(c==‘a‘)||(c==‘e‘)||(c==‘o‘)||(c==‘i‘)||(c==‘u‘)||(c==‘A‘)||(c==‘E‘)||(c==‘O‘)||(c==‘I‘)||(c==‘U‘); 查看详情

2018秋招小红书算法方向在线编程题(代码片段)

代码如下：classTreeNode:def__init__(self,x):self.left=Noneself.right=Noneself.value=xdefBuildTree(ceng,zhong):iflen(ceng)==0:returnNoneiflen(ceng)==1:returnTreeNode(ceng[0])else:flag=TreeNode(ceng[0])root= 查看详情

秋招面试题系列---java工程师(代码片段)

前言：七月末八月初的时候，秋招正式打响，公司会放出大量的全职和实习岗位。为了帮助秋招的小伙伴们，学长这里整理了一系列的秋招面试题给大家，所以小伙伴们不用太过焦虑，相信你们一定能超常... 查看详情

秋招面试题系列---java工程师(代码片段)

决战秋招的前端面试，前端大厂面试手册必不可少(代码片段)

目录准备面试简历个人信息教育经历实习/工作经验项目简历专业技能准备面试复习前端基础计算机网络前端框架数据结构与算法准备面试简历对于简历来说，不需要非常的复杂，简历就是要以比较简洁的方式，让阅... 查看详情

决战秋招的前端面试，前端大厂面试手册必不可少(代码片段)

2023秋招的第一个意向书(代码片段)

...023的第一个offer，把喜气传给大家，祝愿小伙伴在秋招中offer拿到手软。本篇博客主要和大家分享一下这段时间的学习过程，给大家一些参考。下面是字节的意向书👇：1.自我介绍大家好，我叫柳小葱，... 查看详情

2023秋招的第一个意向书(代码片段)

美团2019秋招后台开发编程题题解(代码片段)

图的遍历题目描述给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点，那么总路程至少是多少？输入第一行包含一个整数N，1≤N≤105。接下来N-1行，每行... 查看详情

记一道数字旋转排列算法题(代码片段)

记一道数字旋转排列算法题面试的时候遇到一道算法题，当时没做出来，也没有什么思路。睡觉前突然想到解法，记录一下。题的大意如下，数字以1开始，并围绕1做逆时针旋转，其中1的坐标为(0,0)，如下图所示：要求给一个坐... 查看详情

一道算法题-换钱(代码片段)

　　题目：给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim代表要找的钱数，求换钱有多少种方法。代码如下：　　1#include<iostream>2#include<vector&... 查看详情

一道小面试算法题的思路(代码片段)

一道小算法题的思路有这么一道小面试算法题：给定一个长度为n的整数数组，下标为i的元素表示第i天某个股票的价格，每次最多持有一股，每次买卖最多一股，在最多只买卖一次的情况下（先买后卖，不考虑融券等复杂形式）... 查看详情

数据挖掘2020奇安信秋招算法方向试卷3笔试题解析(代码片段)

来自牛客网：【2020】奇安信秋招算法方向试卷31、设计一个判别表达式中左，右括号是否配对出现的算法，采用____数据结构最佳答案：栈2、对于有n个结点的二叉树,其高度为()答案：未知，可以随意变换高... 查看详情

秋招已过，各大厂的面试题分享一波附c++实现(代码片段)

　　数据结构和算法是面试的一座大山，尤其去面试大厂更是必不可少！简单说明一下为啥喜欢考数据结构和算法，首先，算法有用也没用，如果是中小型企业的简单业务逻辑，可能用不到啥算法，但大厂一定会用到，都知道数... 查看详情

2019vivo秋招提前批笔试题第3题(代码片段)

笔试的时候没做出来，就顺手截图了。虽然知道要用动态规划做，但我一直就不太懂动态规划。笔试完又花了2小时把它做出来了。也不知道性能怎么样，但还好做出来了。defsolution(n,toltal_money,until_price,until_hot):#二维数组，每一... 查看详情

复杂链表的复制（一道算法题）(代码片段)

这是一道算法题。想写篇blog记录一下这道题的解法。题目是这样的：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（... 查看详情

一天一道算法题——树状数组(代码片段)

题目【模板】树状数组1：https://www.luogu.com.cn/problem/P3374树状数组和线段树差不多，可以处理区间操作，但是处理不了太复杂的区间问题。，不过代码比线段树简洁很多很多！！！时间复杂度都为O（logn）。例如，区间[1,8]存储方... 查看详情