[Luogu 1073] NOIP2009 最优贸易

---

分层图，跑最长路。

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

#include 
    
     #include 
     
      #include 
      
       #include 
       
        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
        
          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; }