【每日算法】基础算法——Floyd求最短路（四十九）|算法|Floyd算法-多源汇最短路问题题目内容给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。
数据保证图中不存在负权回路。
输入格式第一行包含三个整数n，m，k
接下来m行，每行包含三个整 ...
Read more
【每日算法】基础算法——SPFA判断负环（四十八）|算法|SPFA算法题目内容给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式如果图中存在负权回路，则输出“Yes”，否则输出“No”。
数 ...
Read more
【每日算法】基础算法——SPFA求最短路（四十七）|算法|SPFA题目内容给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。
数据保证不存在负权回路。
输入格式第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向 ...
Read more
【每日算法】基础算法——求有边数限制的最短路（四十六）|算法|Bellman-Ford算法题目内容给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。
注意：图中可能 存在负权回路 。
输入格式第一行包含三个整数n，m，k。
接下来m行，每行包含三个整数x，y， ...
Read more
【每日算法】基础算法——Dijkstra求最短路2（四十五）|算法|堆优化的dijkstra算法题目内容给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式输出一个整数，表 ...
Read more
【每日算法】基础算法——Dijkstra求最短路1（四十四）|算法|Dijkstra题目内容给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式输出一个整数，表示 ...
Read more
【每日算法】基础算法——有向图的拓扑序列（四十三）|算法|拓扑排序-宽度优先遍历算法题目内容给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入格式第一行包含两个整数n和 ...
Read more
【每日算法】基础算法——图中点的层次（四十二）|算法|树与图的广度优先遍历题目内容给定一个n个点m条边的有向图，图中可能存在重边和自环。
所有边的长度都是1，点的编号为1~n。
请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。
输入格式第一行包含两个整数n和m。
接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。
输出格式输 ...
Read more
【每日算法】基础算法——树的重心（四十一）|算法|树与图的深度优先遍历题目内容给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式第一行包含整数n，表示树的结点数。 ...
Read more
