题解 P1073 【最优贸易】
感谢QWK同学巨佬提供解题思路。@Qin_Wei_Kai_MISAKI
本蒟蒻不会分层图，dp蒟蒻，tarjan不会（滑稽）
看到没有同类题解，来发一发，顺便测了一下hack数据，发现似乎还可以
不喜勿喷
下面开始讲思路：
方法：bfs+spfa
首先我们需要筛出来从1出发可以到达，并且还可以到达n的点。并将它们打上标记。
只有它们是可以走的（很好理解吧，如果从出发点到不了这个点或者还到不了终点，这个点就是无意义的）。
如何打标记呢？两遍建图跑bfs。先正向建图，之后反向建图。
处理完毕之后，就来到了这个思想的核心部分——spfa
有人看了可能一头雾水，spfa不是跑最短路的吗，这题也没有边权啊。
说是spfa，其实是伪的spfa，只是借鉴了spfa的思路。
**重点来了！敲黑板**
首先将所有的标记的点全部扔进队列中，用一个dis数组来记录。 dis数组记录的是什么呢？是从起点到这个点所能买进的最小价值。
举个例子，起点的点权（就是买卖价值）为6，接着连着点权为2的值，之后为4，那么点权为4的点连接的点，如果这个点的点权值大于2，那么就将这个点的点权变为2。
if(dis[to]>dis[t]) dis[to] = dis[t];
这样枚举每一个点，如果这个点的点权值被更新并且这个点不在队列中，就将这个点推进队列（spfa）；
最后枚举每一个点，用当前点的卖出值（点权值）减去这个点的dis值（买进）值，然后取最大的就是答案。
多说无益，上代码。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
int vis[100005];
int vis2[100005];
int a[100005];
int head[100005];
int cnt = 1;
int v[100005];
int dis[100005];
int n,m;
int x2[100005];
int y2[100005];
int z2[100005];
struct edge
{
int to;
int next;
}eg[500005];
void add(int x,int y)
{
eg[cnt].to = y;
eg[cnt].next = head[x];
head[x] = cnt++;
}
void ycl1(int start)
{
queue <int> Q;
Q.push(start);
vis[start] = 1;
while(!Q.empty())
{
int t = Q.front();
Q.pop();
for(int i = head[t];i;i = eg[i].next)
{
int to = eg[i].to;
if(!vis[to])
{
vis[to] = 1;
Q.push(to);
}
}
}
}
void ycl2(int start)
{
queue <int> Q;
Q.push(start);
vis2[start] = 1;//这个数组代表本次（第二次）哪个能到
vis[start]++;
while(!Q.empty())
{
int t = Q.front();
Q.pop();
for(int i = head[t];i;i = eg[i].next)
{
int to = eg[i].to;
if(!vis2[to])
{
vis2[to] = 1;
vis[to]++;
Q.push(to);
}
}
}
}
void spfa(int start)
{
queue <int> Q;
for(int i = 1;i<=n;i++)//先把能到的推进去，dis值代表买进最小值
{
if(vis[i]==2)
{
Q.push(i);
dis[i] = a[i];
}
}
v[start] = 1;
while(!Q.empty())
{
int t = Q.front();
Q.pop();
v[t] = 0;
for(int i = head[t];i;i = eg[i].next)
{
int to = eg[i].to;
if(dis[to]>dis[t]&&vis[to]==2)//关键处，spfa的思想
{
dis[to] = dis[t];
if(!v[to])
{
Q.push(to);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);//读进来
}
for(int i = 1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x2[i] = x;//第一遍建图，为了方便先存起来，第二次再调出来
y2[i] = y;
z2[i] = z;
if(z==1)
{
add(y,x);//加边咯
}else
{
add(y,x);
add(x,y);
}
}
ycl1(n);//从n开始搜索，看到哪个点能到
cnt = 1;
memset(head,0,sizeof(head));
memset(eg,0,sizeof(eg));
for(int i = 1;i<=m;i++)//正向建图
{
if(z2[i]==1)
{
add(x2[i],y2[i]);
}else
{
add(y2[i],x2[i]);
add(x2[i],y2[i]);
}
}
ycl2(1);//从1开始跑一遍
spfa(1);
int ma = -1;
for(int i = 1;i<=n;i++)
{
if(vis[i]==2)
{
ma = max(ma,a[i]-dis[i]);//最后答案，卖出-买入，取最大值
}
}
printf("%d",ma);
return 0;
}
```