[codevs1557]热浪

本题地址： http://www.luogu.org/problem/show?pid=1339

　　　　　http://www.tyvj.cn/p/1031

题目描述

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。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)最小的总费用。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【样例说明】
5->6->1->4 (3 + 1 + 3)

思路

　　一道极好的用来练最短路的题，给出SPFA算法的标准程序，注释详尽

const maxp=10000;//最大节点数

var p,c,s,t:longint;//p:节点数；c:边数；s：起点；t：终点
    a,b:array[1..maxp,0..maxp] of longint;
    //a[x,y]表示x,y边的权；
    //b[x,c]表示与x边相连的第c条边的另一个节点；
    //b[x,0]表示和结点x有多少条边相连；
    d:array[1..maxp] of longint;//队列
    v:array[1..maxp] of boolean;//是否入队标记
    f:array[1..maxp] of longint;//第i个点到起点的最短路
    head,tail:longint;//队尾队首指针

procedure init;
var i,x,y,z:longint;
begin
    read(p,c,s,t);
    for i:=1 to c do
        begin
            readln(x,y,z);//x,y为两个点，z为权值
            inc(b[x,0]);
            b[x,b[x,0]]:=y;
            a[x,y]:=z;
            inc(b[y,0]);
            b[y,b[y,0]]:=x;
            a[y,x]:=z;
        end;
end;

procedure spfa(s:longint);
var i,j,now,sum:longint;
begin
    fillchar(d,sizeof(d),0);
    fillchar(v,sizeof(v),false);
    for i:=1 to p do f[i]:=maxint;
    f[s]:=0;//不要忘了这一句：起点到起点自身的距离为零！
    v[s]:=true;
    d[1]:=s;
    head:=1;
    tail:=1;
    while head<=tail do//队列不空
        begin
            now:=d[head];//取队首元素
            for i:=1 to b[now,0] do//把和对首相连的边全部扫描一遍
                if f[b[now,i]]>f[now]+a[now,b[now,i]] then
//如果和now相连的第i个点（阿尔法点）到起点的最短路还要小于到now节点的最短路与从now结点到阿尔法点的距离则更新
                    begin
                        f[b[now,i]]:=f[now]+a[now,b[now,i]];
                        if not (v[b[now,i]]) then
                            begin
                                inc(tail);
                                d[tail]:=b[now,i];
                                v[b[now,i]]:=true;
                            end;
                    end;
              v[now]:=false;//松弛结点
              inc(head);//出队
        end;
end;

begin
    init;
    spfa(s);
    writeln(f[t]);
end.

View Code