这是我高一的时候NOIP2009提高组的第三题，赛场上直接A了，于是就省一了，也让我还能在信息组混到现在，虽然时间有点久了，不过还是写一下作为纪念。
代码是我当时还以Pascal为主的时候写的，貌似论坛上有些OIer是Pascal选手，相信这样就没有阅读障碍了吧。
（感觉Pascal实在是缺乏C++的美……）

【问题描述】

C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分 为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。 C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价 格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。 商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息 之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城 市的标号从 1~ n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的 过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方 式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另 一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定 这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。 假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路 为单向通行，双向箭头表示这条道路为双向通行。

假设 1~n 号城市的水晶球价格分别为 4，3，5，6，1。 阿龙可以选择如下一条线路：1->2->3->5，并在 2 号城市以 3 的价格买入水晶球，在 3 号城市以 5的价格卖出水晶球，赚取的旅费数为 2。 阿龙也可以选择如下一条线路 1->4->5->4->5，并在第 1 次到达 5 号城市时以 1 的价格 买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。

现在给出 n个城市的水晶球价格，m条道路的信息（每条道路所连接的两个城市的编号 以及该条道路的通行情况） 。请你告诉阿龙，他最多能赚取多少旅费。

【输入】

输入文件名为 XXXXXXXX。

第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的 数目。

第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城 市的商品价格。

接下来 m行， 每行有 3 个正整数， x， y， z， 每两个整数之间用一个空格隔开。 如果 z=1， 表示这条道路是城市 x到城市 y之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市 y之间的双向道路。

【输出】

输出文件 trade.out 共1 行， 包含 1 个整数， 表示最多能赚取的旅费。 如果没有进行贸易， 则输出 0。

【输入输出样例】

5 5

4 3 5 6 1

1 2 1

1 4 1

2 3 2

3 5 1

--------------------------------------------------------------------------------

4 5 2

5

【数据范围】

输入数据保证 1 号城市可以到达 n号城市。

对于 10%的数据，1≤n≤6。

对于 30%的数据，1≤n≤100。

对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。

对于 100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市 水晶球价格≤100。

=========================================================我是华丽分割线=========================================================

题意简述：

在一张有n个点，m条边的图中，任意两个点之间最多只有一条路直接相连。这 m 条道路中有一部分为有向，一部分无向。同一种商品在不同点的价格不一定相同。求从点1出发经过点n的路线中通过一次买卖能赚取的最大差价。

算法描述：

该题有多种做法，例如SPFA，缩圈DP，但像缩圈这样的东西已经超出了NOIP的考察范围，在此暂不讨论，接下来讲一讲SPFA的思路。

看到这样的题，第一反应就是图论题，而且是道求某种最值的题，于是在NOIP的范围内立刻就能想到最短路。然而题目要的是最大值，不是最小值，怎么办？其实最短路算法能求的不仅仅只是最短路。以两点之间差价为边权构图，可以发现这题要求的是一条经过n的路径中一段连续路径的最大值，而且路径中可能有负权边，加上数据范围是100000，可知用SPFA最合适。

普通的SPFA是每次从队列中取出一个点，从它开始更新，对比当前最短路与已知最短路，若当前最短路小，那么就更新最短路估计值，并将被更新的点入队，该过程称为“Relax”。那么将其推广开来，用f[i,0，0]表示到i的最优值，f[i,0,1]表示贸易路径（就是整条路径中进行贸易的那一段）以i结尾的最优值（由于只能贸易一次，所以要用一条以i结尾的贸易路径来推出下一条贸易路径），将f的第二个参数（f[i,□,1]）改成1表示的含义与以上相同，只不过路径必须经过n。这样一来，设j为与i相邻之点（即存在Edge[i,j]）就可以用f[i,0,0]和f[i,0,1]推出f[j,0,0]，用f[i,0,1]推出f[j,0,1]，同理，当第二个参数为1时一样转移，即可得出结果。最后输出Max{f[i,1,0]}(1<=i<=n)。

当然SPFA不但可以像这样基于边，还可以基于点，有兴趣的OIer可以自行研究。

My Code:

program trade;
const
    FileName='trade';
    MaxN=100000;
    MaxM=500000;
var
    n,m,EdgeNum,QHead,QTail,Ans:longint;
    Price,Head:array[0..MaxN]of longint;
    Next,Target,v,Queue:array[0..MaxM*2]of longint;
    Flag,Used:array[0..MaxN]of boolean;
    f:array[0..MaxN,0..1,0..1]of longint;

procedure AddEdge(const x,y,c:longint);
begin
    inc(EdgeNum);
    Next[EdgeNum]:=Head[x];
    Head[x]:=EdgeNum;
    Target[EdgeNum]:=y;
    v[EdgeNum]:=c;
end;

procedure Init;
var
    i,x,y,z:longint;
begin
    readln(n,m);
    for i:=1 to n do
        read(Price[i]);
    for i:=1 to m do
    begin
        readln(x,y,z);
        AddEdge(x,y,Price[y]-Price[x]);
        if z=2 then AddEdge(y,x,Price[x]-Price[y]);
    end;
end;

procedure InQueue(const x:longint);
begin
    if Flag[x] then exit;
    inc(QTail);
    Queue[QTail]:=x;
    Flag[x]:=True;
end;

function OutQueue(var x:longint):boolean;
begin
    if QHead=QTail then exit(False);
    inc(QHead);
    x:=Queue[QHead];
    Flag[x]:=False;
    exit(True);
end;

procedure SPFA;
var
    x,i:longint;
begin
    InQueue(1);
    for i:=1 to n-1 do
    begin
        f[i,1,0]:=-(Maxlongint shr 1);
        f[i,1,1]:=-(Maxlongint shr 1);
    end;
    while OutQueue(x) do
    begin
        i:=Head[x];
        while i>0 do
        begin
            if f[x,0,0]>f[Target[i],0,0] then
            begin
                f[Target[i],0,0]:=f[x,0,0];
                InQueue(Target[i]);
            end;
            if f[x,0,1]+v[i]>f[Target[i],0,0] then
            begin
                f[Target[i],0,0]:=f[x,0,1]+v[i];
                InQueue(Target[i]);
            end;
            if f[x,0,1]+v[i]>f[Target[i],0,1] then
            begin
                f[Target[i],0,1]:=f[x,0,1]+v[i];
                InQueue(Target[i]);
            end;
            ///////////////////////////////////////////
            if Target[i]=n then
            begin
                if f[x,0,0]>f[Target[i],1,0] then
                begin
                    f[Target[i],1,0]:=f[x,0,0];
                    InQueue(Target[i]);
                end;
                if f[x,0,1]+v[i]>f[Target[i],1,0] then
                begin
                    f[Target[i],1,0]:=f[x,0,1]+v[i];
                    InQueue(Target[i]);
                end;
                if f[x,0,1]+v[i]>f[Target[i],1,1] then
                begin
                    f[Target[i],1,1]:=f[x,0,1]+v[i];
                    InQueue(Target[i]);
                end;
            end;
            ///////////////////////////////////////////
            if f[x,1,0]>f[Target[i],1,0] then
            begin
                f[Target[i],1,0]:=f[x,1,0];
                InQueue(Target[i]);
            end;
            if f[x,1,1]+v[i]>f[Target[i],1,0] then
            begin
                f[Target[i],1,0]:=f[x,1,1]+v[i];
                InQueue(Target[i]);
            end;
            if f[x,1,1]+v[i]>f[Target[i],1,1] then
            begin
                f[Target[i],1,1]:=f[x,1,1]+v[i];
                InQueue(Target[i]);
            end;
            ///////////////////////////////////////////
            if not Used[Target[i]] then
            begin
                InQueue(Target[i]);
                Used[Target[i]]:=True;
            end;
            i:=Next[i];
        end;
    end;
end;

procedure Print;
var
    i:longint;
begin
    for i:=1 to n do
        if f[i,1,0]>Ans then Ans:=f[i,1,0];
    writeln(Ans);
end;

begin
    assign(input,FileName+'.in');
    assign(output,FileName+'.out');
    reset(input);
    rewrite(output);
    Init;
    SPFA;
    Print;
    close(input);
    close(output);
end.