Feng003

图论

codeforces(2) DP(3) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 算法课课程作业(4) 题解(6)

/ 注册

全部文章 / 图论（共1篇）

分层最短路（计蒜客 - A1958 ）

问题：给定一张有n个点，m条有向边的图。一个整数k。（n<=1e5,m<=2e5,k<=10）。你有k次机会使得图中的某一条边权值变为0。求1号点到n号点的最短距离。保证至少存在一条路径从1到n。思路：dijkstra算法+dp转移　　这其实就是一道分层最短路的模板题。普通的d...

dijkstra 分层最短路

2020-04-12

0 570