题解 | 最优贸易-NOIP2009提高组复赛
最优贸易
https://ac.nowcoder.com/acm/contest/257/C
算法知识点: SPFA
复杂度： )
解题思路：
先求出：
- 从
走到
的过程中，买入水晶球的最低价格
；
- 从
的过程中，卖出水晶球的最高价格
；
然后枚举每个城市作为买卖的中间城市，求出 的最大值即可。
求 和
时，由于不是拓扑图，状态的更新可能存在环，因此不能使用动态规划，只能使用求最短路的方式。
C++ 代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; const int N = 100010,
M = 2000010;
int n, m;
int price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmax[N], dmin[M];
bool st[N];
void add(int *h, int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void spfa(int *d, int sign)
{
queue<int> q;
memset(st, false, sizeof st);
if (sign == 1) memset(d, 0x3f, sizeof dmax);
if (sign == 1) q.push(1), st[1] = true;
else q.push(n), st[n] = true;
while (q.size())
{
int t = q.front();
q.pop();
for (int i = sign == 1 ? h[t] : rh[t]; ~i; i = ne[i])
{
int j = e[i];
if (sign == 1 && d[j] > min(d[t], price[j]) || sign == -1 && d[j] < max(d[t], price[j]))
{
if (sign == 1) d[j] = min(d[t], price[j]);
else d[j] = max(d[t], price[j]);
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
for (int i = 1; i <= n; i++) scanf("%d", &price[i]);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(h, a, b), add(rh, b, a);
if (c == 2) add(h, b, a), add(rh, a, b);
}
spfa(dmin, 1);
spfa(dmax, -1);
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
printf("%d\n", res);
return 0;
} 报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ
查看34道真题和解析