Dij:
inline void Dijkstra()
{
q.push(make_pair(0,1));
dis[1]=0;
while(!q.empty())
{
int x=q.top().first,y=q.top().second;//权值和点
q.pop();
if(vis[y])continue;
vis[y]=1;
for(int i=head[y];i;i=G[i].next)
{
int v=G[i].v;
//if(vis[v])continue;
if(dis[y]+G[i].w<dis[v])
{
dis[v]=dis[y]+G[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
SPFA:
dis[s]=0;
vis[s]=1;
q.push(s);
while(q.size())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
可以发现, SPFA 内部