【题解】LuoGu3003：[USACO10DEC]苹果交货Apple Delivery

原题传送门
贝西有两个又香又脆的红苹果要送给她的两个朋友。当然她可以走的C（1<=C<=200000）条“牛路”都被包含在一种常用的图中，包含了P（1<=P<=100000）个牧场，分别被标为1…P。没有“牛路”会从一个牧场又走回它自己。“牛路”是双向的，每条牛路都会被标上一个距离。最重要的是，每个牧场都可以通向另一个牧场。每条牛路都连接着两个不同的牧场P1_i和P2_i（1<=P1_i,p2_i<=P)，距离为D_i。所有“牛路”的距离之和不大于2000000000。

现在，贝西要从牧场PB开始给PA_1和PA_2牧场各送一个苹果（PA_1和PA_2顺序可以调换），那么最短的距离是多少呢？当然，PB、PA_1和PA_2各不相同。

输入输出格式
输入格式：

• Line 1: Line 1 contains five space-separated integers: C, P, PB, PA1, and PA2

• Lines 2…C+1: Line i+1 describes cowpath i by naming two pastures it connects and the distance between them: P1_i, P2_i, D_i

输出格式：

• Line 1: The shortest distance Bessie must travel to deliver both apples
  输入样例
  9 7 5 1 4
  5 1 7
  6 7 2
  4 7 2
  5 6 1
  5 2 4
  4 3 2
  1 2 3
  3 2 2
  2 6 3
  输出样例
  12

这道题是裸的最短路，
贝茜的走法只有两种：pb->pa1->pa2或pb->pa2->pa1
所以我们只需算出每个点到pa1、pa2的最短路即可

But，本题数据范围有点大，作为一个pascal选手，懒得打堆优dij（手打堆可真麻烦），就写写SPFA吧。spfa太不稳定了，所以我想起了看到过的一个优化版SPFA，

即：若新加入到队尾的点到源点的最短路小于队首的，则给它加入到队首
实现code（其中u为新加入节点）：

if dis[u] < dis[q[h + 1]] then swap(q[t], q[h + 1]);

嗯，就加了这么一句话时间上优化了很多，不过spfa在考场上还是太虚，我不敢用，又手打了一遍堆优dij的

code:
spfa版本

uses math;
var
    edge : array[0..400000] of record
        t, len, next : longint;
    end;
    head, dis, q : array[0..400000] of int64;
    vis : array[0..200000] of boolean;
    n, m, pb, pa1, pa2, x, y, z, ans, num, i : longint;

procedure swap(var x, y : int64);
var
    tmp : int64;

begin
    tmp := x; x := y; y := tmp;
end;

procedure add(x, y, z : longint);

begin
    inc(num);
    edge[num].t := y;
    edge[num].len := z;
    edge[num].next := head[x];
    head[x] := num;
end;

procedure spfa(s : longint);
var
    h, t, e, i, u, sum : longint;

begin
    for i := 1 to n do dis[i] := maxlongint;
    dis[s] := 0;
    fillchar(vis, sizeof(vis), 0);
    h := 0; t := 1; q[1] := s;
    while h < t do
    begin
        inc(h);
        e := q[h];
        vis[e] := false;
        i := head[e];
        while i <> 0 do
        begin
            u := edge[i].t;
            if dis[u] > dis[e] + edge[i].len then
            begin
                dis[u] := dis[e] + edge[i].len;
                if not vis[u] then
                begin
                    inc(t);
                    q[t] := u;
                    if dis[u] < dis[q[h + 1]] then swap(q[t], q[h + 1]);
                end;
            end;
            i := edge[i].next;
        end;
    end;
    sum := dis[pb];
    if s <> pa1 then inc(sum, dis[pa1]) else inc(sum, dis[pa2]);
    ans := min(ans, sum);
end;

begin
    readln(m, n, pb, pa1, pa2);
    for i := 1 to m do
    begin
        readln(x, y, z);
        add(x, y, z);
        add(y, x, z);
    end;
    ans := maxlongint;
    spfa(pa1);
    spfa(pa2);
    writeln(ans);
end.

dijkstra版本

uses math;
var
    edge : array[0..400000] of record
        t, len, next : longint;
    end;
    heap : array[0..400000] of record
        node, len : int64;
    end;
    head, dis : array[0..400000] of int64;
    vis : array[0..200000] of boolean;
    n, m, pb, pa1, pa2, x, y, z, ans, num, i, len : longint;

procedure swap(var x, y : int64);
var
    tmp : int64;

begin
    tmp := x; x := y; y := tmp;
end;

procedure add(x, y, z : longint);

begin
    inc(num);
    edge[num].t := y;
    edge[num].len := z;
    edge[num].next := head[x];
    head[x] := num;
end;

procedure push(u, l : int64);
var
    i : longint;

begin
    inc(len);
    i := len;
    heap[i].node := u; heap[i].len := l;
    while i > 1 do
    begin
        if heap[i].len < heap[i >> 1].len then
        begin
            swap(heap[i].node, heap[i >> 1].node);
            swap(heap[i].len, heap[i >> 1].len);
            i := i >> 1;
        end else break;
    end;
end;

procedure pop;
var
    i, x : longint;

begin
    heap[1] := heap[len];
    dec(len);
    i := 1;
    while (i << 1) <= len do
    begin
        if ((i << 1) or 1 > len) or (heap[i << 1].len < heap[(i << 1) or 1].len) then
            x := i << 1 else x := (i << 1) or 1;
        if heap[i].len > heap[x].len then
        begin
            swap(heap[i].node, heap[x].node);
            swap(heap[i].len, heap[x].len);
            i := x;
        end else break;
    end;
end;

procedure dijkstra(s : longint);
var
    u, l, v, sum : int64;
    i : longint;

begin
    for i := 1 to n do dis[i] := maxlongint;
    dis[s] := 0;
    fillchar(vis, sizeof(vis), 0);
    len := 0;
    push(s, 0);
    while len > 0 do
    begin
        u := heap[1].node; l := heap[1].len;
        pop;
        if vis[u] then continue;
        vis[u] := true;
        i := head[u];
        while i <> 0 do
        begin
            v := edge[i].t;
            if dis[v] > l + edge[i].len then
            begin
                dis[v] := l + edge[i].len;
                push(v, dis[v]);
            end;
            i := edge[i].next;
        end;
    end;
    sum := dis[pb];
    if s <> pa1 then inc(sum, dis[pa1]) else inc(sum, dis[pa2]);
    ans := min(ans, sum);
end;

begin
    readln(m, n, pb, pa1, pa2);
    for i := 1 to m do
    begin
        readln(x, y, z);
        add(x, y, z);
        add(y, x, z);
    end;
    ans := maxlongint;
    dijkstra(pa1);
    dijkstra(pa2);
    writeln(ans);
end.