【JAVA】滴滴-2021校招在线笔试-DE数据开发试卷-0913

我会带着你远行 2022-12-06 15:06 160阅读 0赞

### 目录 ###

*  前言
 *  一、D星群岛（全A，A了0.82的人考虑一下：四个岛，现在有两条桥1-2 3-4）
 *   *  代码：
 *  二、毕业旅行（全A）
 *   *  代码：

# 前言 #

兄弟们都会有offer的，不要慌，奥力给  
![在这里插入图片描述][2020091321000936.png_pic_center]  
![在这里插入图片描述][20200913210515118.png_pic_center]

# 一、D星群岛（全A，A了0.82的人考虑一下：四个岛，现在有两条桥1-2 3-4） #

时间限制： 3000MS  
内存限制： 589824KB

**题目描述：**  
D星群岛由n个小岛组成。为了加强小岛居民之间的交流，头目决定启动一个造桥工程，将全部n个岛连接到一起。

由于受到金融危机的影响，头目要求造桥的总成本要最少，并且还规定每一座桥的成本都不能超过k万D星币。

需要注意的是，由于受到地理环境和气候影响，有些小岛之间没有办法直接造桥。

现在给你m条小岛之间的造桥成本数据以及k的值，请问这个宏伟的造桥工程是否能够顺利完成？

注意：可能边不够，也可能费用超支。

**输入描述**  
多组输入，第1行输入一个正整数T表示输入数据的组数。  
对于每一组输入数据：输入m+1行。  
第1行包含三个正整数，分别表示n、m和k，n≤100，m≤1000，k≤10000，三个数字之间用空格隔开。  
接下来m行表示m条小岛之间的造桥成本数据，每一行包含三个正整数，分别表示两个小岛的编号（从1开始）和这两个小岛之间的造桥成本（单位：万）。

**输出描述**  
针对每一组输入数据，如果能够完成造桥工程输出“Yes”，否则输出“No”。

**样例输入**  
2  
3 3 400  
1 2 200  
1 3 300  
2 3 500  
3 3 400  
1 2 500  
1 3 600  
2 3 700

**样例输出**  
Yes  
No

## 代码： ##

package didi;
    
    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: * @Email: * @Date: 2020/9/13 * @Time: 19:43 * @Version: 1.0 * @Description: Description */
    public class First3 { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int T = scanner.nextInt();
            for (int l = 0; l < T; l++) { 
                int n = scanner.nextInt();
                int m = scanner.nextInt();
                int k = scanner.nextInt();
                ArrayList<Integer[]> bridges = new ArrayList<>();
                for (int i = 0; i < m; i++) { 
                    Integer[] bridge = new Integer[2];
                    for (int j = 0; j < bridge.length; j++) { 
                        bridge[j] = scanner.nextInt();
                    }
                    if (scanner.nextInt() <= k) { 
                        bridges.add(bridge);
                    }
                }
                /*if (bridges.size() < n - 1) {//三个岛最少也得有两座桥 System.out.println("No"); } else { System.out.println("Yes"); //透风小技巧 只写这部分，不写下面的能A36% }*/
                HashSet<Integer> connections = new HashSet<Integer>();
                if (!bridges.isEmpty()) { 
                    connections.add(bridges.get(bridges.size() - 1)[0]);
                    connections.add(bridges.get(bridges.size() - 1)[1]);
                    bridges.remove(bridges.size() - 1);
                }
                while (true) { 
                    boolean end = true;
                    for (int i = bridges.size() - 1; i > -1; i--) { 
                        if (connections.contains(bridges.get(i)[0])
                                || connections.contains(bridges.get(i)[1])) { 
                            connections.add(bridges.get(i)[0]);
                            connections.add(bridges.get(i)[1]);
                            bridges.remove(i);
                            end = false;
                        }
                    }
                    if (end) { 
                        break;
                    }
                }
                if (connections.size() == n) { 
                    System.out.println("Yes");
                } else { 
                    System.out.println("No");
                }
            }
            scanner.close();
        }
    }

# 二、毕业旅行（全A） #

时间限制： 3000MS  
内存限制： 589824KB

**题目描述：**  
小滴正在筹划他的毕业旅行。他打算去找他的外国网友们，首先第一站是法国巴黎，但是去巴黎的路线有很多，交通工具也有很多可供选择。

现在有一个结点数为n，边的条数为m的无向图表示小滴到巴黎的所有路线。其中小滴的家为结点s，巴黎为结点e，小滴出发时间为start，请问小滴最早什么时候能到达巴黎？

**输入描述**  
单组输入，数字间有空格隔开。

第一行两个整数：结点数n，边数m（n<=1000,m<=10000）。

第二行到第m+1行每行各有三个整数：结点u，结点v，需要的时间time（1<=u,v<=n，time<50，time以小时为单位）。

最后一行为家的位置：s，巴黎的位置：e，出发时间start（1<=s,e<=n，出发时间格式为month.day/hour，小时为24小时制，出发年份默认为2020年，且一定会在2020年到达，数据保证有解。）

**输出描述**  
最早能到达巴黎的时间e time（格式与出发时间格式相同）。

**样例输入**  
4 4  
1 2 5  
1 3 6  
2 4 8  
3 4 6  
1 4 7.9/8

**样例输出**  
7.9/20

**提示**  
**输入样例2**  
4 4  
1 2 25  
1 3 18  
2 4 28  
3 4 22  
1 4 7.9/8

**输出样例2**  
7.11/0

## 代码： ##

package didi;
    import java.util.*;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/9/13 * @Time: 20:13 * @Version: 1.0 * @Description: Description */
    
    
    public class Second2 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) { 
                int n = sc.nextInt();
                int m = sc.nextInt();
                List<int[]>[] ways = new List[n + 1];
                for (int i = 0; i < n + 1; i++) { 
                    ways[i] = new ArrayList<>();
                }
                for (int i = 0; i < m; i++) { 
                    int l = sc.nextInt();
                    int r = sc.nextInt();
                    int cost = sc.nextInt();
                    int[] lr = { r, cost};
                    ways[l].add(lr);
                    int[] rl = { l, cost};
                    ways[r].add(rl);
                }
                int start = sc.nextInt();
                int tar = sc.nextInt();
                String time = sc.next();
    
                int[] arrived = new int[n + 1];
                Arrays.fill(arrived, Integer.MAX_VALUE);
                Deque<int[]> list = new LinkedList<>();
                list.add(new int[]{ start, 0});
                while (!list.isEmpty()) { 
                    int[] cur = list.poll();
                    int pos = cur[0];
                    int cost = cur[1];
                    if (cost < arrived[pos]) { 
                        arrived[pos] = cost;
                        for (int[] arr : ways[pos]) { 
                            if (arr[1] + cost < arrived[arr[0]]) { 
                                list.add(new int[]{ arr[0], arr[1] + cost});
                            }
                        }
                    }
                }
                int res = arrived[tar];
                String out = help(res, time);
                System.out.println(out);
            }
        }
    
        static int[] months = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
        public static String help(int res, String time) { 
            String[] temp = time.split("\\.");
            int month = Integer.parseInt(temp[0]);
            temp = temp[1].split("/");
            int day = Integer.parseInt(temp[0]);
            int hour = Integer.parseInt(temp[1]);
    
            hour += res;
            if (hour >= 24) { 
                day += hour / 24;
                hour = hour % 24;
            }
            while (day > months[month]) { 
                day -= months[month];
                month++;
            }
            StringBuilder arrive = new StringBuilder();
            arrive.append(month).append(".")
                    .append(day).append("/").append(hour);
    
            return arrive.toString();
        }
    }

[2020091321000936.png_pic_center]: /images/20221123/1d6a850befa04a26aca43ae277b3fb72.png
[20200913210515118.png_pic_center]: /images/20221123/3c93d734df354816bcb64ffcb61dca0b.png