大学里到树木要打药

题目描述

教室外有 $N$ 棵树（树的编号从 $0\sim N-1$），根据不同的位置和树种，学校要对其上不同的药。

因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。

对于树的药是成区间分布，比如 $3 \sim 5$ 号的树靠近下水道，所以他们要用驱蚊虫的药， $20 \sim 26$ 号的树，他们排水不好，容易涝所以要给他们用点促进根系的药 $\cdots$诸如此类。

每种不同的药要花不同的钱。

现在已知共有 $M$ 个这样的区间，并且给你每个区间花的钱，问最后这些树木要花多少药费。

输入描述

每组输入的第一行有两个整数 $N$和 $M$。$N$ 代表马路的共计多少棵树，$M$ 代表区间的数目，$N$ 和 $M$ 之间用一个空格隔开。

接下来的 $M$ 行每行包含三个不同的整数，用一个空格隔开，分别表示一个区域的起始点 $L$ 和终止点 $R$ 的坐标，以及花费。

$1\leq L\leq R \leq N \leq 10^6,1\leq M\leq 10^5$，保证花费总和不超过 int 范围。

输出描述

输出包括一行，这一行只包含一个整数，所有的花费。

输入输出样例

示例

输入

500 3 
150 300 4
100 200 20 
470 471 19

输出

2662

运行限制

语言	最大运行时间	xxxxxxxxxx15 1import os2import sys3​4# 请在此输入您的代码5n = int(input())6a = list(map(int, input().split()))7a.sort()8b = []9c = []10for i in range(n):11    if a[i] % 2 == 0:12        b.append(a[i])13    else:14        c.append(a[i])15print(“ “.join(map(str, c)),” “.join(map(str,b)))python
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

大学里的树木要维护

题目描述

教室外有 $N$ 棵树（树的编号从 $1\sim N$），根据不同的位置和树种，学校已经对其进行了多年的维护。

因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。

由于已经维护了多年，每一个树都由学校的园艺人员进行了维护费用的统计。

每棵树的前期维护费用各不相同，但是由于未来需要要打药，所以有些树木的维护费用太高的话，就要重新种植。

由于维护费用也称区间分布，所以常常需要统一个区间里的树木的维护开销。

现给定一个长度为 $N$ 的数组 $A$ 以及 $M$ 个查询，$A_i$ 表示第 $i$ 棵树到维护费用。对于每个查询包含一个区间，园艺人员想知道该区间内的树木维护的开销是多少。

请你编写程序帮帮他！

输入描述

每组输入的第一行有两个整数 $N$和 $M$。$N$ 代表马路的共计多少棵树，$M$ 代表区间的数目，$N$ 和 $M$ 之间用一个空格隔开。

接下来的一行，包含 $N$ 个数 $A_1,A_2,\cdots,A_N$，分别表示每棵树的维护费用，每个数之间用空格隔开。

接下来的 $M$ 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点 $L$ 和终止点 $R$ 的坐标。

输出描述

输出包括 $M$ 行，每一行只包含一个整数，表示维护的开销。

输入输出样例

示例

输入

10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7

输出

24
22
17

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

合根植物

题目描述

$w$ 星球的一个种植园，被分成 $m \times n$ 个小格子（东西方向 $m$ 行，南北方向 $n$ 列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

输入描述

第一行，两个整数 $m,n$，用空格分开，表示格子的行数、列数（$1 \leq m,n \leq 1000$）。

接下来一行，一个整数 $k$ ($0 \leq k \leq 10^5$ )，表示下面还有 $k$ 行数据。

接下来 $k$ 行，每行两个整数 $a，b$，表示编号为 $a$ 的小格子和编号为 $b$ 的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：$5 \times 4$ 的小格子，编号：

1 2 3 4 
5 6 7 8
9 10 11 12
13 14 15 16 
17 18 19 20

输出描述

输出植物数量。

输入输出样例

示例

输入

5 4
16 
2 3 
1 5
5 9
4 8 
7 8
9 10
10 11
11 12 
10 14
12 16 
14 18
17 18
15 19
19 20
9 13
13 17

输出

5

样例说明

其合根情况参考下图：

运行限制

语言	最大运行时间	最大运行内存
C++	2s	256M
C	2s	256M
Python3	2s	256M
Java	2s	256M

修改数组

题目描述

给定一个长度为 $N$ 的数组 $A = [A_1,A_2,··· ,A_N]$，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改$A_2,A_3,··· ,A_N$。

当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1$ ∼ $A_i−1$ 中出现过。如果出现过，则小明会给 $A_i$ 加上 1 ；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 1 ，直 到 $A_i$ 没有在 $A_1$ ∼ $A_i−1$ 中出现过。

当 $A_N$ 也经过上述修改之后，显然 $A$ 数组中就没有重复的整数了。

现在给定初始的 $A$ 数组，请你计算出最终的 $A$ 数组。

输入描述

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,··· ,A_N$。

其中，$1 \leq N \leq 10^5，1 \leq A_i \leq 10^6$。

输出描述

输出 $N$ 个整数，依次是最终的 $A_1,A_2,··· ,A_N$。

输入输出样例

示例

输入

5 
2 1 1 3 4

输出

2 1 3 4 5

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Python3	1s	256M
Java	1s	256M

分巧克力

题目描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i \times Wi$ 的方格组成的长方形。为了公平起见，

小明需要从这 $N$ 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数;

2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

第一行包含两个整数 $N,K$ ($1 \leq N, K \leq 10^5$)。

以下 N 行每行包含两个整数 $H_i,W_i$ ($1 \leq H_i, W_i \leq 10^5$)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长。

输入输出样例

示例

输入

2 10 
6 5
5 6

输出

2

运行限制

语言	最大运行时间	最大运行内存
C++	2s	256M
C	2s	256M
Python3	2s	256M
Java	2s	256M

M次方根

题目描述

小$A$最近在学高等数学，他发现了一道题，求三次根号下 $27$。

现在已知，小$A$开始计算，$1$ 的三次方得 $1$， $2$ 的三次方得 $8$ ，$3$ 的三次方得 $27$，然后他很高兴的填上了 $3$。接着他要求 $5$ 次根号下 $164$。

然后他开始 $1$ 的三次方得 $1$， $2$ 的三次方得 $8$ ，$3$ 的三次方得$27\cdots$

直到他算到了秃头，也没有找到答案。

这时一旁的小$B$看不下去了，说这题答案又不是个整数。

小$A$震惊，原来如此。

作为程序高手的小$A$，打算设计一个程序用于求解 $M$ 次跟下 $N$ 的值。

但是由于要考虑精度范围，答案必须要保留 $7$ 位小数，三次根号下 $27$ 都要掰手指的小$A$又怎么会设计呢。

请你帮小$A$设计一个程序用于求解 $M$ 次根号 $N$。

输入描述

每组输入的第一行有两个整数 $N$ 和 $M$，数据间用空格隔开。

$1\leq N \leq 10^5$，$1\leq M \leq 10^2$，$M < N$。

输出描述

输出一个实数表示答案（请保留小数点后 $7$ 位）。

输入输出样例

示例

输入

27 3

输出

3.0000000

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

找零问题

题目描述

蓝桥商店的老板需要找零 $n$ 元钱。

钱币的面额有：$100$ 元、$50$ 元、$20$ 元、$5$ 元、$1$ 元，问如何找零使得所需钱币的数量最少？

注意：$n$ 可能为 $0$，也能为几百元（别问，问就是来着里微信提现来了）

输入描述

在第一行给出测试例个数 $N$，代表需要找零的钱数。

$1\leq N \leq 10^5$。

输出描述

输出共有 $5$ 行，每一行输出数据输出找零的金额与数量，详情看样例。

示例

输入

365

输出

100:3 50:1 20:0 5:3 1:0

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

小B的宿舍

题目描述

小B的宿舍楼沿着走廊南北向的两边各有 $200$ 个房间，如下所示：

[房间1][房间3][房间5][房间7][房间9 ]...[房间399]
---------------------------------------------- 走廊 ---------------------------------------------- 
[房间2][房间4][房间6][房间8][房间10]...[房间400]

最近，由于转专业和专业分流的原因，宿舍将迎来新的调整，以便组成新的班级后方便管理。

但是由于走廊狭窄，走廊里只能通过一个搬运的物品（可以同向也可以反向），因此必须指定高效的搬运计划。

老师给了每位同学下达了以下要求，让同学们体现收拾好行李，然后给每位同学 $10$ 分钟的时间搬运。

当从房间 $i$ 搬运行李到 $j$ 时，$i$ 与 $j$ 之间的走廊都会被占用。所以，$10$ 分钟之内同一段走廊最多 $1$ 个人同时搬运，不重叠的走廊也可以同时搬运。

小B的老师是个数学老师，经过运筹学一通计算他得到了最优的搬运计划。

虽然计划不唯一，但是最优值唯一，请问这个最短时间是多少？

输入描述

输入数据有 $T$ 组测试例，在第一行给出测试例个数 $T$。

每个测试例的第一行是一个整数 $N$（$1\leq N \leq 200$)，表示要搬运行李的人数。

接下来 $N$ 行，每行两个正整数 $s$ 和 $t$，表示一个人，要将行李是从房间 $s$ 移到到房间 $t$。

输出描述

每组输入都有一行输出数据，为一整数 $Time$，表示完成任务所花费的最小时间。

示例

输入

3 
4
10 20
30 40
50 60
70 80 
2
1 3
2 200
3
10 100 
20 80
30 50

输出

10
10
20

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

数字三角形

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 $N\ (1 \leq N \leq 100)$，表示三角形的行数。

下面的 $N$ 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

5 
7 
3 8
8 1 0
2 7 4 4 
4 5 2 6 5

输出

27

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Python3	1s	256M
Java	1s	256M

游戏中的学问

题目描述

大家应该都见过很多人手拉手围着篝火跳舞的场景吧？一般情况下，大家手拉手跳舞总是会围成一个大圈，每个人的左手拉着旁边朋友的右手，右手拉着另一侧朋友的左手。

不过，如果每一个人都随机的拉住两个不同人的手，然后再慢慢散开，事情就变得有趣多了——此时大家依旧会形成圈，不过却可能会形成多个独立的圈。当然这里我们依然要求一个人的右手只能拉另一个人的左手，反之亦然。

班里一共有 $N$ 个同学，由 $1$ 到 $N$ 编号。Will 想知道，究竟有多少种本质不同的拉手方案，使得最终大家散开后恰好形成 $k$ 个圈呢？

给定两种方案，若存在一个人和他的一只手，满足在这两种方案中，拉着这只手的人的编号不同，则这两种方案本质不同。

输入描述

输入一行包含三个正整数$N,k,P$。

其中，$3 \leq k \leq N \leq 3000$，$10^4 \leq p \leq 2 \times 10^9$。

输出描述

输出一行一个整数，表示本质不同的方案数对 $p$ 的余数。保证 $p$ 一定是一个质数。

输入输出样例

示例 1

输入

3 1 1000000009

输出

2

运行限制

语言	最大运行时间	最大运行内存
C++	2s	128M
C	2s	128M
Python3	2s	128M
Java	2s	128M

跳跃

题目描述

小蓝在一个 $n$ 行 $m$ 列的方格图中玩一个游戏。

开始时，小蓝站在方格图的左上角，即第 $1$ 行第 $1$ 列。

小蓝可以在方格图上走动，走动时，如果当前在第 $r$ 行第 $c$ 列，他不能走到行号比 $r$ 小的行，也不能走到列号比 $c$ 小的列。同时，他一步走的直线距离不超过 $3$。

例如，如果当前小蓝在第 $3$ 行第 $5$ 列，他下一步可以走到第 $3$ 行第 $6$ 列、第 $3$ 行第 $7$ 列、第 $3$ 行第 $8$ 列、第 $4$ 行第 $5$ 列、第 $4$ 行第 $6$ 列、第 $4$ 行第 $7$ 列、第 $5$ 行第 $5$ 列、第 $5$ 行第 $6$ 列、第 $6$ 行第 $5$ 列之一。

小蓝最终要走到第 $n$ 行第 $m$ 列。

在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。

小蓝希望，从第 $1$ 行第 $1$ 列走到第 $n$ 行第 $m$ 列后，总的权值和最大。请问最大是多少？

输入描述

输入的第一行包含两个整数 $n, m$，表示图的大小。

接下来 $n$ 行，每行 $m$ 个整数，表示方格图中每个点的权值。

其中，$1 \leq n \leq 100，-10^4 \leq 权值 \leq 10^4$。

输出描述

输出一个整数，表示最大权值和。

输入输出样例

示例 1

输入

3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4

输出

15

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

小明的背包1

题目描述

小明有一个容量为 $V$ 的背包。

这天他去商场购物，商场一共有 $N$ 件物品，第 $i$ 件物品的体积为 $w_i$，价值为 $v_i$。

小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 $1$ 行包含两个正整数 $N,V$，表示商场物品的数量和小明的背包容量。

第 $2\sim N+1$ 行包含 $2$ 个正整数 $w,v$，表示物品的体积和价值。

$1\leq N\leq10^2$，$1\leq V \leq 10^3$，$1 \leq w_i,v_i \leq10^3$。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

示例 1

输入

5 20 
1 6
2 5
3 8
5 15
3 3

输出

37

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

小明的背包2

题目描述

小明有一个容量为 $V$ 的背包。

这天他去商场购物，商场一共有 $N$ 种物品，第 $i$ 种物品的体积为 $w_i$，价值为 $v_i$，每种物品都有无限多个。

小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 $1$ 行包含两个正整数 $N,V$，表示商场物品的数量和小明的背包容量。

第 $2\sim N+1$ 行包含 $2$ 个正整数 $w,v$，表示物品的体积和价值。

$1\leq N\leq10^3$，$1\leq V \leq 10^3$，$1 \leq w_i,v_i \leq10^3$。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

示例 1

输入

5 20
1 6 
2 5
3 8
5 15 
3 3

输出

120

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Python3	1s	256M
Java	1s	256M

小明的背包3

题目描述

小明有一个容量为 $V$ 的背包。

这天他去商场购物，商场一共有 $N$ 种物品，第 $i$ 种物品的体积为 $w_i$，价值为 $v_i$，数量为 $s_i$。

小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 $1$ 行包含两个正整数 $N,V$，表示商场物品的数量和小明的背包容量。

第 $2\sim N+1$ 行包含 $3$ 个正整数 $w,v,s$，表示物品的体积和价值。

$1\leq N\leq10^2$，$1\leq V \leq 2\times10^2$，$1 \leq w_i,v_i,s_i \leq 2\times10^2$。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

示例 1

输入

3 30 
1 2 3 
4 5 6
7 8 9

输出

39

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Python3	1s	256M
Java	1s	256M

蓝肽子序列

题目描述

L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。

生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。

具体的，一个蓝肽可以使用 $1$ 至 $5$ 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。

在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。

如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。

给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。

输入描述

输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。

其中有 ，两个字符串的长度均不超过 $1000$。

输出描述

输出一个整数，表示最长的那个公共蓝肽子序列的长度。

输入输出样例

示例

输入

LanQiaoBei 
LanTaiXiaoQiao

输出

2

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

合唱队形

题目描述

$N$ 位同学站成一排，音乐老师要请其中的 $(N-K)$ 位同学出列，使得剩下的 $K$ 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 $K$ 位同学从左到右依次编号为 $1，2，\cdots K$，他们的身高分别为 $T_1，T_2，\cdots，T_K$， 则他们的身高满足 $T_1< \cdots < T_i> T_{i+1}> \cdots >T_K(1 \leq i \leq K)$。

你的任务是，已知所有 $N$ 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述

输入两行。

第一行是一个整数 $N\ (2 \leq N \leq 100)$，表示同学的总数。

第二行有 $n$ 个整数，用空格分隔，第 $i$ 个整数 $T_i(130 \leq T_i \leq 230)$ 是第 $i$ 位同学的身高(厘米)。

输出描述

输出一个整数，就是最少需要几位同学出列。

输入输出样例

示例 1

输入

8
186 186 150 200 160 130 197 220

输出

4

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

最优包含

题目描述

我们称一个字符串 $S$ 包含字符串 $T$ 是指 $T$ 是 $S$ 的一个子序列，即可以从字符串 $S$ 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 $T$ 完全一样。

给定两个字符串 $S$ 和 $T$，请问最少修改 $S$ 中的多少个字符，能使 $S$ 包含 $T$ ？

其中，$1 \leq |T| \leq |S| \leq 1000$。

输入描述

输入两行，每行一个字符串。

第一行的字符串为 $S$，第二行的字符串为 $T$。

两个字符串均非空而且只包含大写英文字母。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

ABCDEABCD
XAABZ

输出

3

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Python3	1s	256M
Java	1s	256M

路径

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M

蓝桥王国

题目描述

小明是蓝桥王国的王子，今天是他登基之日。

在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。

题目的内容如下：

蓝桥王国一共有 $N$ 个建筑和 $M$ 条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为 $1\sim N$ 。（其中皇宫的编号为 $1$）

国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。

输入描述

输入第一行包含三个正整数 $N,M$。

第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\rightarrow v$ 之间存在一条距离为 $w$ 的路。

$1\leq N \leq 3\times10^5$，$1 \leq m \leq 10^6$，$1 \leq u_i, v_i\leq N$，$0 \leq w_i \leq 10 ^ 9$。

输出描述

输出仅一行，共 $N$ 个数，分别表示从皇宫到编号为 $1\sim N$ 建筑的最短距离，两两之间用空格隔开。（如果无法到达则输出 $-1$）

输入输出样例

示例 1

输入

3 3
1 2 1 
1 3 5
2 3 2

输出

0 1 3

运行限制

语言	最大运行时间	最大运行内存
C++	2s	512M
C	2s	512M
Python3	2s	512M
Java	2s	512M

随机数据下的最短路问题

题目描述

给定 $N$ 个点和 $M$ 条单向道路，每条道路都连接着两个点，每个点都有自己编号，分别为 $1\sim N$ 。

问你从 $S$ 点出发，到达每个点的最短路径为多少。

输入描述

输入第一行包含三个正整数 $N,M,S$。

第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\rightarrow v$ 之间存在一条距离为 $w$ 的路。

$1\leq N \leq 5\times10^3$，$1 \leq M \leq 5\times 10^4$，$1 \leq u_i, v_i\leq N$，$0 \leq w_i \leq 10 ^ 9$。

本题数据随机生成。

输出描述

输出仅一行，共 $N$ 个数，分别表示从编号 $S$ 到编号为 $1\sim N$ 点的最短距离，两两之间用空格隔开。（如果无法到达则输出 $-1$）

输入输出样例

示例 1

输入

3 3 1
1 2 1 
1 3 5
2 3 2

输出

0 1 3

运行限制

语言	最大运行时间	最大运行内存
C++	1s	128M
C	1s	128M
Python3	1s	128M
Java	1s	128M