tlqtj(bushi
by _JTG_rabbit_ @ 2022-11-23 20:18:19
还有我这个玄学做法，竟然也过了
```cpp
#include <bits/stdc++.h>
#define MAX 600000
#define INF 2147483647
using namespace std;
struct edge
{
long long next;
long long to;
long long dis;
}e[MAX*10];
long long pr[MAX],dis2[MAX],visit[MAX],head[MAX],que[MAX*10],hp=0,tp=0,nume=0,ans2=0;
long long n,m,s,u,v,w;
void adde(long long from,long long to)
{
e[++nume].next=head[from];
e[nume].to=to;
e[nume].dis=pr[to]-pr[from];
head[from]=nume;
}
int main()
{
scanf("%d%d",&n,&m);
for(long long i=1;i<=n;i++)
scanf("%d",&pr[i]);
for(long long i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(w==1)adde(u,v);
else if(w==2)
{
adde(u,v);
adde(v,u);
}
}
for(int i=1;i<=n;i++)
dis2[i]=INF;
hp=0;tp=0;
dis2[1]=0;visit[1]=1;
que[++hp]=1;++tp;
while(hp<=tp)
{
int top=que[hp];
que[hp]=0;visit[top]=0;
for(int i=head[top];i!=0;i=e[i].next)
{
int to=e[i].to;
if((max(dis2[top],e[i].dis)>dis2[to]||dis2[to]==INF)&&dis2[top]!=INF)
{
dis2[to]=max(dis2[top],e[i].dis);
if(!visit[to])
{
que[++tp]=to;
visit[to]=1;
}
}
}
hp++;
}
printf("%d",dis2[n])；
return 0;
}
```
(P.S:人为加了反作弊)
by w9095 @ 2022-11-30 09:34:30