```
#include <bits/stdc++.h>
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define in inline
#define re register
using namespace std;
typedef long long ll;
typedef double db;
in int read()
{
int ans=0,f=1;char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) ans=(ans<<3)+(ans<<1)+(c^48);
return ans*f;
}
in int cmin(int &a,int b) {return a=min(a,b);}
in int cmax(int &a,int b) {return a=max(a,b);}
int n,m;
int a[1000005];
int nex[2000005],tail[2000005],head[1000005],tot;
int st[2000005],en[2000005];
void addedge(int u,int v)
{
nex[++tot]=head[u];
head[u]=tot;
tail[tot]=v;
}
int dfn[1000005],scc[1000005],maxx[1000005],minn[1000005],cnt;
stack<int> s;
int tarjan(int u) //tarjan algorithm
{
dfn[u]=++cnt;
int low=dfn[u];
s.push(u);
for (int e=head[u];e;e=nex[e])
{
int v=tail[e];
if (!dfn[v])
{
int lowv=tarjan(v);
low=min(low,lowv);
}
else if (!scc[v])
{
low=min(low,dfn[v]);
}
}
if (low==dfn[u])
{
while (!s.empty())
{
int w=s.top();s.pop();
scc[w]=u;
maxx[u]=max(maxx[u],a[w]);
minn[u]=min(minn[u],a[w]);
if (w==u) break;
}
}
return low;
}
int ans=0;
int dfs(int u,int &x) //solving the problem
{
int ret=maxx[u];
if (u==scc[n])
{
ans=max(ans,maxx[u]-minn[u]);
x=1;
return maxx[u];
}
for (int e=head[u];e;e=nex[e]) //looking for a node which can be reached by u and can reach scc[n] with the maximum price
{
int v=tail[e],xx=0;
int res=dfs(v,xx);
if (!xx) return 0;
x=1;
ret=max(ret,res);
}
ans=max(ans,ret-minn[u]);
return ret;
}
int main()
{
memset(minn,0x3f,sizeof(minn));
n=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
for (int j=1;j<=z;j++)
{
addedge(x,y);
st[tot]=x,en[tot]=y;
swap(x,y);
}
}
tarjan(1);
memset(head,0,sizeof(head));
memset(tail,0,sizeof(tail));
memset(nex,0,sizeof(nex));
int tmp=tot;
tot=0;
for (int i=1;i<=tmp;i++)
{
if (scc[st[i]] && scc[st[i]]!=scc[en[i]]) addedge(scc[st[i]],scc[en[i]]);
}
dfs(scc[1],tmp);
cout<<ans<<endl;
return 0;
}
```
by Thomasguo666 @ 2020-01-08 21:11:49
这题不是bfs就行吗
by yummy @ 2020-01-08 21:17:42
我看不懂，告辞
by Int_Main_ @ 2020-01-08 21:17:48
qndmx
by Sya_Resory @ 2020-01-08 21:18:00
@[yummy](/user/101694) 然而我把tarjan写出来了还调了一个晚上
by Thomasguo666 @ 2020-01-08 21:19:02
@[Thomasguo666](/user/107935) 就因为你用的tarjan才会调一个晚上啊
by yummy @ 2020-01-08 21:23:22
@[yummy](/user/101694) 所以tarjan到底哪里不好了
by Thomasguo666 @ 2020-01-08 21:25:38
去泥马的萌新
by Sai0511 @ 2020-01-08 21:49:09