[Luogu 1073] NOIP2009 最优贸易

<题目链接>

---

分层图，跑最长路。

真不是我恋旧，是我写的 Dijkstra 求不出正确的最长路，我才铤而走险写 SPFA 的…

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

const int MAXN = 100010;

int n, m, value[MAXN];

struct Graph

{

    struct Edge

    {

        int to, w;

        Edge *next;

        Edge(int to, int w, Edge* next): to(to), w(w), next(next) {}

        ~Edge(void)

        {

            if(next != NULL)

                delete next;

        }

    }*head[MAXN * 3];

    Graph(int n)

    {

        std :: fill(head, head + n * 3 + 1, (Edge*)NULL);

        head[n] = new Edge(0, 0, head[n]);

        head[n * 3] = new Edge(0, 0, head[n * 3]);

    }

    ~Graph(void)

    {

        for(int i = 0; i <= n * 3; ++i)

            delete head[i];

    }

    void AddEdge(int u, int v)

    {

        head[u] = new Edge(v, 0, head[u]);

        head[u] = new Edge(v + n, -value[u], head[u]);

        head[u + n] = new Edge(v + n, 0, head[u + n]);

        head[u + n] = new Edge(v + n * 2, value[u], head[u + n]);

        head[u + n * 2] = new Edge(v + n * 2, 0, head[u + n * 2]);

    }

}*G;

namespace SPFA

{

    bool exist[MAXN * 3];

    int dist[MAXN * 3];

    std :: queue<int> Q;

    void SPFA(void)

    {

        memset(dist, 0xc0, sizeof dist);

        Q.push(1);

        exist[1] = true;

        dist[1] = 0;

        while(!Q.empty())

        {

            int u = Q.front(), v;

            Q.pop();

            exist[u] = false;

            for(Graph :: Edge *i = G -> head[u]; i != NULL; i = i -> next)

                if(dist[v = i -> to] < dist[u] + i -> w)

                {

                    if(!exist[v])

                        Q.push(v);

                    dist[v] = dist[u] + i -> w;

                }

        }

    }

}

int main(void)

{

    scanf("%d %d", &n, &m);

    G = new Graph(n);

    for(int i = 1; i <= n; ++i)

        scanf("%d", &value[i]);

    for(int i = 1, x, y, z; i <= m; ++i)

    {

        scanf("%d %d %d", &x, &y, &z);

        G -> AddEdge(x, y);

        if(z == 2)

            G -> AddEdge(y, x);

    }

    SPFA :: SPFA();

    printf("%d\n", SPFA :: dist[0]);

    delete G;

    return 0;

}