P1073 最优贸易
n 个城市间以 m 条有向道路连接, 小 T 从 1 号城市出发, 将
要去往 n 号城市.
小 T 观察到一款商品 Z 在不同的城市的价格可能不尽相同,
小 T 想要在旅行中的某一个城市购买一件商品 Z, 在另一个
城市卖出. 因为旅途劳顿, 这种买卖小 T 只打算做一次.
请问小 T 能够获得的最大收益是多少?
求点$1$到所有点的最小值，再从$n$出发判断所能够到达，取最大值即可
更新最小值方法与spfa类似
#include<bits/stdc++.h> #define N 1010101
using namespace std; int d[N],n,head[N],tot,phead[N],w[N],m,ans,tpt,dd[N];
struct node {
int to,next;
} e[N],p[N];
void add(int u,int v) {
e[++tot].to=v,e[tot].next=head[u],head[u]=tot;
}
void padd(int u,int v){
p[++tpt].to=v,p[tpt].next=phead[u],phead[u]=tpt;
} queue<int>Q;
bool vis[N];
void spfa() {
memset(vis,,sizeof(vis));
memset(d,0x7f,sizeof(d));
Q.push();vis[]=;
while(!Q.empty()){
int u=Q.front();Q.pop();vis[u]=;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to,minn=min(d[u],w[u]);
if(minn<d[v]){
d[v]=minn;
if(!vis[v]){
Q.push(v);
vis[v]=;
}
}
}
}
} void sspfa(){
memset(vis,,sizeof(vis));
memset(dd,0x7f,sizeof(dd));
Q.push(n);vis[n]=,dd[n]=;
while(!Q.empty()){
int u=Q.front();Q.pop();vis[u]=;
for(int i=phead[u];i;i=p[i].next){
int v=p[i].to;
if(dd[v]>dd[u]+){
dd[v]=dd[u]+;
if(!vis[v]){
Q.push(v);
vis[v]=;
}
}
}
}
} int main() {
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++) scanf("%d",&w[i]);
for(int x,y,z,i=; i<=m; i++) {
scanf("%d%d%d",&x,&y,&z);
if(z==) add(y,x);
add(x,y);
if(z==) padd(x,y);
padd(y,x);
}
spfa();
sspfa();
for(int i=;i<=n;i++){
if(dd[i]<dd[])
ans=max(ans,w[i]-d[i]);
}
printf("%d\n",ans);
return ;
}