2001
T4 Car的旅行路线
ybt luogu
建图+最短路
1.建图时细节较多 已知三点求第四点的坐标 勾股定理判断斜边
2.最短路时多起点多终点
2013
D1T3 货车运输
ybt luogu
最大生成树+倍增LCA
答案的边一定在最大生成树上
将原图建出最大生成树
在树上使用倍增LCA提取路径
2014
D2T2 寻找道路
ybt luogu
正反图
先建反图求出能到达终点的点
然后处理出能在最短路上的点
跑最短路就ok
ybt luogu
建图+最短路
1.建图时细节较多 已知三点求第四点的坐标 勾股定理判断斜边
2.最短路时多起点多终点
ybt luogu
最大生成树+倍增LCA
答案的边一定在最大生成树上
将原图建出最大生成树
在树上使用倍增LCA提取路径
ybt luogu
正反图
先建反图求出能到达终点的点
然后处理出能在最短路上的点
跑最短路就ok