SPFA&邻接表 PASCAL

题目来自CODE[VS]-->热浪

1557 热浪

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石

题目描述 Description

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入描述 Input Description

第一行: 4个由空格隔开的整数: T, C, Ts, Te

第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出描述 Output Description

一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

样例输入 Sample Input

7 11 5 4

2 4 2

1 4 3

7 2 2

3 4 3

5 7 5

7 3 3

6 1 1

6 3 4

2 4 3

5 6 3

7 2 1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

5->6->1->4 (3 + 1 + 3)

var
    n,m,i,t,w,d,s,e,x,y,z:longint;
    next,a,v,c:array[1..101000]of longint;
    head,f:array[1..10010]of longint;
    u:array[1..10010]of boolean;

procedure init;
    begin
        readln(n,m,s,e);        //读入
        for i:=1 to m do
            begin
                readln(x,y,z);
                next[2*i-1]:=head[x];        //next记录下一个与x相连的边对应的i
                head[x]:=i*2-1;        //当前x对应的i
                a[2*i-1]:=y;        //记录边
                v[2*i-1]:=z;        //记录边权
                    next[2*i]:=head[y];
                    head[y]:=2*i;
                    a[2*i]:=x;
                    v[2*i]:=z;            //注意双向道路
            end;
        for i:=1 to n do
            f[i]:=maxlongint;        //初始化
        f[s]:=0;
    end;

procedure spfa;            //SPFA
    begin
        t:=1; w:=1;        //t:头指针; w:尾指针;
        c[t]:=s; u[s]:=true;    //c:队列; u:记录是否在队列中
        while t<>w+1 do
            begin
                d:=head[c[t]];
                while d<>0 do
                    begin
                        if f[c[t]]+v[d]<f[a[d]] then    
                            begin
                                f[a[d]]:=f[c[t]]+v[d];    //对a[d]的距离进行更新
                                if not u[a[d]] then        //当a[d]不在队列中时
                                    begin
                                        inc(w);
                                        c[w]:=a[d];
                                        u[a[d]]:=true;
                                    end;
                            end;
                        d:=next[d];        //用邻接表查找下一个与c[t]相邻的点
                    end;
                u[c[t]]:=false;        //将c[t]出队
                inc(t);        //头指针后移一位
            end;
    end;

procedure output;
    begin
        writeln(f[e]);
    end;

begin
    init;
    spfa;
    output;
end.