算法1:分层图spfa
最好理解的方法。
建三层图直接跑spfa。
第二层买第三层卖求最长路。
C++ 代码
/*
* @Author : Zed
* @Date : 2022-01-14 18:28:30
* @LastEditors : Zed
* @LastEditTime : 2022-03-31 15:32:02
* @Description : file content
* @FilePath : \Acm\2test.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define fl(x, i) (x + i * n)
const int N = 500010, M = 200010;
vector<PII> E[N];
bool v[N];
int n, m, d[N];
queue<PII> q;
void spfa(int sta)
{
memset(d, -0x3f3f3f, sizeof d);
memset(v, 0, sizeof v);
d[sta] = 0;
v[sta] = 1;
q.push(make_pair(d[sta], sta));
while (q.size())
{
int x = q.front().second;
q.pop();
v[x] = 0;
for (auto [y, len] : E[x])
{
if (d[y] < d[x] + len)
{
d[y] = d[x] + len;
if (!v[y])
{
q.push({-d[y], y});
v[y] = 1;
}
}
}
}
}
signed main()
{
int s;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int gg;
scanf("%d", &gg);
E[fl(i, 0)].push_back({fl(i, 1), -gg});
E[fl(i, 1)].push_back({fl(i, 2), gg});
}
for (int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
E[fl(x, 0)].push_back({fl(y, 0), 0});
E[fl(x, 1)].push_back({fl(y, 1), 0});
E[fl(x, 2)].push_back({fl(y, 2), 0});
if (z == 2)
{
E[fl(y, 0)].push_back({fl(x, 0), 0});
E[fl(y, 1)].push_back({fl(x, 1), 0});
E[fl(y, 2)].push_back({fl(x, 2), 0});
}
}
spfa(fl(1, 0));
cout << d[fl(n, 2)] << endl;
return 0;
}
算法2:两遍spfa/dij
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
const int N = 500010, M = 200010;
int h[N], h2[N], ne[N], e[N], val[N], tot, dmin[N], dmax[N];
bool v[N];
int n, m;
queue<PII> q;
void add(int x, int y, int *h)
{
e[++tot] = y;
ne[tot] = h[x];
h[x] = tot;
}
// void dijkstra(int beg)
void spfa(int sta, int *d, int *h, bool flag)
{
if (flag)
memset(d, 0x3f3f3f, sizeof dmin);
memset(v, 0, sizeof v);
d[sta] = val[sta];
v[sta] = 1;
q.push(make_pair(d[sta], sta));
while (q.size())
{
int x = q.front().second;
q.pop();
v[x] = 0;
for (int i = h[x]; i; i = ne[i])
{
int y = e[i];
// cout << d[y] << endl;
if ((flag && d[y] > min(d[x], val[y])) || (!flag && d[y] < max(d[x], val[y])))
{
if (flag)
d[y] = min(d[x], val[y]);
else
d[y] = max(d[x], val[y]);
if (!v[y])
{
q.push(make_pair(-d[y], y));
v[y] = 1;
}
}
}
}
}
signed main()
{
int s;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d", &val[i]);
}
for (int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, h);
add(y, x, h2);
if (z == 2)
{
add(y, x, h);
add(x, y, h2);
}
}
// dijkstra(s);
spfa(1, dmin, h, true);
spfa(n, dmax, h2, false);
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, dmax[i] - dmin[i]);
cout << ans;
}