hnust_yangyanjun

分类

大数加法(1) 尺取法(1) 面经(4) 题解(119)

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共4篇）

逛公园来自专栏

题意：有一个n个节点，m条有向边的图，如果从1到n的最短路为d，请你求从1到n的路线长度小于d+k的数目，答案对p取模。思路：最短路+记忆化搜索反向建图求每一个节点到n节点的最短距离。定义状态dp[i][j]为从节点i，还可以额外多走j的长度的状态到目标状态( dp[n][ji] (k>=j...

最短路记忆化搜索

2021-04-23

3 814

[JSOI2015]地铁线路来自专栏

题意：有n个站点，m条路线，每条路线使用一次要交1块钱，给出每条路线的信息，从一个站点到下一个站点的时间为1，让你求从一个站点到另一个站点的最小花费是多少，此时花费时间最大为多少？思路：最短路+拓扑+dp一看就是图论题，第一问求最小花费，如何用最短路求呢，对于每一条路线我们要创建两个虚点，一个虚点...

最短路 dp

2021-04-21

2 895

追债之旅

题意：有n个城市，小明再1号城市，它的欠债人在n号城市，城市之间有道路连接，不过需要交路费，而且欠债人每天都会花费一些钱，每天你只能走一条道路从一个城市到另一个城市，求你最少的花费（路费+欠债人花费）为多少？思路：最短路的变形题，多了个欠债人每天的花费。用val[i][j]表示第i天在第j个城市的...

最短路

2020-08-13

1 598

最短路

题目：给一个连通图，每次询问两点间最短路。每条边的长度都是1。思路：看数据范围我们就知道普通的最短路是无法在规定的时间爬完的，所以我们盯上了长度为1，和m<n+100。如果是一颗树，我们可以用Lca求最短路，每一次查询为O(log(n))。我们已知这是一个连通图，所以我们可以用并查集生成最小...

最短路并查集 LCA

2020-07-08

0 684