图论 - 最短路
王雨阳
·
·
个人记录
最优乘车
Description:
有 n 个城市， m 条公交线路， 每一条公交线路经过c座城市，
并且线路是单向的，求从 S 城(编号为 1)到 H 城(编号为 n)的最少换乘次数。
数据范围:
$1≤N≤500
Solve:
可以先将问题转化一下，变为求从起点到终点最少要乘坐多少辆公交车，那么原问题就是新问题的次数再减去一.
建图:
在同一条线路上的站点， 从前往后连一条边权为 1 的边， 表示只需坐一辆车就可以到达。 这样边权都为 1 ，答案就是从 1 号点到 n号点的最短路，可以用01bfs求。
昂贵的聘礼
Description:
一位探险家来到一个印第安部落，他想要得到酋长的一件聘礼， 它可以直接购买，也可以用其他聘礼来换取，不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。其他东西也可以用类似的方式获得。
部落中每一个人都有一个等级， 如果旅行家和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品T_i和该替代品所对应的”优惠”V_i。
如果两人地位等级差距超过了M，就不能”间接交易”。旅行家得到酋长的聘礼至少要花多少金币？
数据范围:
1≤P≤10^4,
1≤L,M≤N,
0≤X<N
Solve:
建图:
如果物品 u 可以换取物品 v， 那就连一条u 到 v 的有向边，边权为T_i, 表示如果已经有了u， 再购买 v，可以花T_i个金币。在建一个虚拟起点 s，并向每一个物品连一条边权为 P的有向边，表示直接购买物品，需要花P个金币,答案就是 s 到 ed 的最短路。
处理等级限制:
M$最大只有$100$， 可以暴力枚举等级区间 $[L,R]$, 表示旅行家只跟等级在 $[L,R]$范围内的人进行交易。总的时间复杂度为$O(N^2 \times N^2logN)
通信线路
Description:
0≤K<N≤10^3 ,
1≤M≤10^4,
1≤w_i≤10^6
### Solve:
二分答案 + __$01bfs$__
实际上，题目就是要从$1$到$n$的路径中使第 $k + 1$大的边权尽可能小。如果一个比较小的$w$ 可以满足条件，那么再大一点一定也可以满足条件，答案具有单调性，可以二分边权$w$，然后将图中边权大于 $w$ 的设为$1$，将边权小于等于 $w$ 的设为 $0$， 用$bfs$求一下从 $1$ 到 $n$ 的最短路，如果 $dist(1, n) > k$说明如果路径中最大边权为 $w$， 则至少要经过大于 $k$ 条边权为$w$ 的边，才能到$n$。如果小于等于$k$，说明 $check$ 成功
## __道路与航线__
### Description:
有一张 $N$ 个点， $M$ 条边的图。这 $n$ 个点由R条道路与P条航线连接，
道路为无向边，航线为有向边，无向边的边权 $> 0$, 有向边的边权可能为负数。
并且如果有一条航线可以从$ A_i $到 $B_i $， 那么不可能通过一些航线和道路从 $B_i$ 到 $A_i$。求从 $S$ 到每个点的最短路。
1≤N≤25000 ,
1≤R,P≤50000,
1≤Ai,Bi,S≤T,
### Solve：
由于数据经过特殊构造，无法用 SPFA算法。 这张图一定是由若干由无向图构成的连通块，外加若干有向边构成的，并且