spfa|9.9 极其简单的最短路问题 2721
- 题目
- 题解
- 代码
题目 小C终于被小X感动了，于是决定与他看电影，然而小X距离电影院非常远，现在假设每条道路需要花费小X的时间为1，由于有数以万计的好朋友沿路祝贺，导致小X在通过某些路不得不耗费1的时间来和他们聊天，尽管他希望尽早见到小C，所以他希望找到一条最快时间到达电影院的路。
一开始小X在1号点，共有N个点，M条路，电影院为T号点。
30%：n<=10 m<=20
60%: n<=1000 m<=20000
100%: n<=5000000 m<=10000000
题解 好的，用spfa就很好，因为出题人好心的把最大的3个测试点开到了10s
时间复杂度O(ve)
【spfa|9.9 极其简单的最短路问题 2721】不过据说原版题目spfa会炸，那么怎么办呢？
由于观察到边权只会是1或2，可以将其拆2的边为1和1，然后直接用bfs即可，复杂度为O（n+m）————
话说你不会忘了bfs怎么打吧？
代码
const
max=20000000;
var
n,m,t,i,j,k,x,z:longint;
ls,d:array[0..5000000]of longint;
ne,y,w:array[0..20000000]of longint;
v:array[0..20000000]of longint;
b:array[0..5000000]of boolean;
procedure spfa;
var
i,k,h,t,x,z:longint;
begin
h:=0;
t:=1;
v[1]:=1;
b[1]:=true;
d[1]:=0;
while h0 do
begin
x:=v[h mod max];
if d[y[k]]=0 then d[y[k]]:=maxlongint;
if d[x]+w[k] 推荐阅读
- 呼市绿地广场景观管理局监察四大队巡查管理2019.9.8.
- 呼市绿地广场景观管理局监察四大队巡查管理2019.9.30.
- 只要9.9元！零基础学习MySQL
- POJ|POJ 1364 King 差分约束系统 SPFA
- 基于汉字字频特征实现99.99%准确率的新闻文本分类器（一）
- 手绘教程|手绘教程 ▏极其详细的手绘教程，只此一家 (四十二)
- 美团一面
- 人为啥不能如初?
- 我的幸福生活2019.9.29
- POJ2240 spfa判增大环 poj3259 spfa判负环