这是 $Dijkstra$。
void dijkstra(int x)
{
priority_queue<pair<int,int>>que;
memset(d,0x3f,sizeof(d));
d[x]=0;
que.push({-d[x],x});
while(!que.empty())
{
int y=que.top().second;
que.pop();
e[y]=true;
for(ri i=f[y];i;i=way[i].h)
{
int z=way[i].to;
if(d[z]>d[y]+way[i].quan)
{
d[z]=d[y]+way[i].quan;
if(!e[z])
{
que.push({-d[z],z});
}
}
}
}
}
时间复杂度 \(O(m\log n)\)。
这是SPFA。
void spfa(int x)
{
queue<int>que;
memset(d,0x3f,sizeof(d));
d[x]=0;
que.push(x);
e[x]=true;
while(!que.empty())
{
int y=que.front();
que.pop();
e[y]=false;
for(int i=f[y];i;i=way[i].h)
{
z=way[i].to;
if(d[z]<d[y]+way[i].quan)
{
d[z]=d[y]+way[i].quan;
if(!e[z])
{
way.push(z);
e[z]=true;
}
}
}
}
}
时间复杂度 \(O(m)\) ~ \(O(nm)\)。
但是,有时我们会遇到边权只有0和1&&数据范围很大的图,这种题的正解往往不是最短路,但是可以拿最短路骗一点分。而0/1最短路的发明,就是为了在这种情况下以更高的效率骗更多的分。
回忆一下 \(Dijkstra\) 为什么比 \(SPFA\) 多个 \(log\),就是因为 \(Dijkstra\) 在维护单调性时使用的优先队列,其内部实现是二叉堆,复杂度 \(O(\log n)\)。但是现在由于只有0/1,故如果想要维护单调性,只需开个双端队列,将0的插到队头,1的插到队尾即可。
代码如下:
il void zerone(int x)
{
deque<int>que;
memset(d,0x3f,sizeof(d));
d[x]=0;
que.push_front(x);
while(!que.empty())
{
int y=que.front();
que.pop_front();
e[y]=true;
for(ri i=f[y];i;i=way[i].h)
{
int z=way[i].to;
if(e[z])
{
continue;
}
d[z]=min(d[z],d[y]+way[i].quan);
if(way[i].quan)
{
que.push_back(z);
}
else
{
que.push_front(z);
}
}
}
}
理论复杂度 \(O(n)\)。
实际上,不只是0/1边权,只要是0和另一正边权的组合都可以如此实现。至于实际应用,自己瞎搞吧。