[Luogu 1073] NOIP2009 最优贸易

时间:2023-03-08 16:50:02
[Luogu 1073] NOIP2009 最优贸易

[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;
}