[模板]spfa+邻接表

发布于 2019-03-31  866 次阅读

就是用了邻接表来储存这个图
进行spfa时可以少进行很多次判断

pascal

type
  arr=record
        x,y,w,next:longint;
      end;
var
  edge:array[0..1000000] of arr;
  ls,t,state:array[0..1000000] of int64;
  exits:array[0..1000000] of boolean;
  i,j,k,n,m,q,p,o,s:longint;
procedure spfa;
var
  head,tail,i,j:longint;
begin
  state[1]:=0;
  head:=0; tail:=1;
  exits[1]:=true;
  t[1]:=1;
  repeat
    inc(head);
    i:=ls[t[head]];
    while i<>0 do
      begin
        with edge[i] do
          begin
            if state[x]+w

c++

#include 
using namespace std;
int i;
struct arr 
{ 
int x,y,w,next;
};
arr edge[10000000];
int state[100000000],t[100000000],ls[100000000];
bool exits[1000000];
int spfa()
{
    int head=0,tail=1;
    t[1]=1; state[1]=0;
    exits[1]=true;
    do
    {
        head++;
        i=ls[t[head]];
        while (i!=0) 
        {
            if (state[edge[i].x]+edge[i].w
]]>