网易2021校招笔试真题

1、仓库配送

【题目描述】

网易严选建有N个自营仓分布在全国各地，标记为仓库1到N。

给定一个配货时间组（v,u,w)，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间。可能存在仓库间过远，无法支持调拨转货。

指定一个出发仓库K，我们需要将供应商发送到K仓库的货配送到各个仓库。问配送到所有可到达仓库所要最短时间？如果无法全部调拨到，则返回-1。

输入描述：

第一行三个正整数，由空格分割，分别表示仓库个数N，出发仓K，以及配送时间组个数M

接下来 M行，每行三个整数，由空格分割，分别表示（v,u,w)三个数，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间

输出描述：

一行一个数字表示答案，配送到所有可达仓库到最短时间

备注：

N的区间是[1, 100] ；

K的区间是[1, N] ；

times的最大长度是[1, 6000] ；

所有边 times[i] = (u, v, w)，1<=u, v <= N 0 <= w <= 100

输入样例：

6 2 5

2 1 1

2 6 2

1 3 3

3 4 1

6 5 2

输出样例：

5

说明：
由图可知，所需最短时间为1+3+1=5

【解题思路】
最短路问题，floyd或者dijkstra都可以

【参考代码】
int floyd(vector<vector<int>>& graph, int N, int source)
{
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
    int ans = INT_MIN;
    for (int i = 1; i <= N; ++i) {
        ans = max(ans, graph[source][i]);
    }
    if (ans == INT_MAX)return -1;
    return ans;
}
int main()
{
    int N, K, M, v, u, w;
    cin >> N >> K >> M;
    vector<vector<int>> graph(N + 1, vector<int>(N + 1, INT_MAX));
    for (int i = 0; i < M; ++i) {
        cin >> v >> u >> w;
        graph[v][u] = w;
    }
    for (int i = 0; i < N; ++i) {
        graph[i][i] = 0;
    }
    cout << floyd(graph, N, K);
    return 0;
}

2、摩尔斯电码解码

【题目描述】

已知摩尔斯电码和字符映射关系如下：

A -> 0

B -> 1

C -> 10

D -> 11

E -> 100

F -> 101

G -> 110

H -> 111

当前我们获取到了一串01数字字符串，需要进行摩尔斯电码解码，请问共有多少种解码方法？

输入描述：

一行由0和1组成的字符串

输出描述：

一行一个数字表示答案，即解码方法数量

备注：

输入字符串长度范围为1～100

输出解码方法数不超过2147483647

输入样例1：

11

输出样例1：

2

说明1：

有D和BB两种解法

输入样例2：

100

输出样例2：

3

说明2：

有E,BAA和CA三种解法

【解题思路】
动态规划求解，注意当遇到字符'1'的时候，有三种翻译的方式

【参考代码】
imp