//尝试tarjan强联通缩点+拓扑
//跑dfs缩点建强联通也可
//关于spfa，它还没si(spfa问就是不会不熟)
//spfa它没si，孩子却要si了，孩子已乱
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef pair<int,int> pii;
const int N=100010,M=1e6+10;
int h[N],e[M],ne[M],idx;    //原图，照样子全部存进去
int h2[N],e2[M],ne2[M],idx2;    //tarjan后的新图
int d[N];  //新图入度
int w[N];   //各个城市的价格(售价和买价相同)

//到每个连通块的最小值，当前连通块的最小值，当前连通块的最大值
int dist[N],mi[N],ma[N];

//tarjan的初始时间戳，能回溯到最早的时间戳，tarjan栈，tarjan标记是否被访问，tarjan时间器，模拟栈顶指针
int dfn[N],low[N],stk[N],v[N],ti,tt=-1;

int id[N],bcnt; //id表示当前点属于哪个连通块
int f[N];   //存答案
queue<int> q;   //全局拓扑，好像不全局也行？
int n,m;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void add2(int a,int b)
{
    e2[idx2]=b,ne2[idx2]=h2[a],h2[a]=idx2++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++ti;
    stk[++tt]=u;
    v[u] = true;

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(v[j])
        {
            low[u]=min(low[u],low[j]);
        }
    }

    int x=-0x3f3f3f3f,y=0x3f3f3f3f; //当前连通块中的最大值和最小值
    if(dfn[u] == low[u])
    {
        ++bcnt; //连通块加1
        int t;  //定义在循环外面啊啊啊啊啊，不然while判断直接G
        do  //出栈到u为止
        {
            t=stk[tt--];
            v[t]=0,id[t]=bcnt;
            x=max(x,w[t]);
            y=min(y,w[t]);
        }while(u != t);
        mi[bcnt]=y,ma[bcnt]=x;  //记录当前连通块的最小最大值
    }
}

void topsort()
{
    for(int i=1;i<=bcnt;i++)
    {
        if(!d[i])   //连通块入度为0
        {
            q.push(i);
        }
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h2[t];i!=-1;i=ne2[i])
        {
            int j=e2[i];
            dist[j]=min(dist[t],mi[j]); //要么是他自己的连通块的最小值，要么就是连边所在的连通块的最小值
            f[j]=max(max(f[t],f[j]),ma[j]-dist[j]); //更新答案，卖出减买入
            if(--d[j] == 0) q.push(j);
        }
    }
}

int main()
{
    //建图还是稍微麻烦了点，用了两个邻接表
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(h2,-1,sizeof h2);

    for(int i=1;i<=n;i++) cin>>w[i];

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(c == 1)
        {
            add(a,b);
        }
        else
        {
            add(a,b),add(b,a);
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i);
    }

    //遍历每个点，寻找不在连通块中的边并新建拓扑图（此时必定合法不存在环）
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            if(id[i] != id[k])  //当前边的两个点不在连通块中说明找到了单向边
            {
                add2(id[i],id[k]);
                d[id[k]]++;
            }
        }
    }

    memset(dist,0x3f,sizeof dist);
    topsort();
    cout<<f[id[n]]; //输出终点所在连通块的答案
    return 0;
}

这是一份错误的代码，但是竟然能ac

这份代码里有两个错误： 错误1：topsort()函数里不应该把所有入度为0的连通块入队，而是应该只把结点1所在的连通块入队，因为题目要求从结点1出发。 可以试一试下面这个样例

input
4 3
100 1 1 100
1 4 1
2 1 1
3 2 1
output
0

如果更正了错误1还有一个样例过不了！

错误2：不应该初始化dist数组为0x3f3f3f3f，应该将结点1所在的连通块入队，并初始化dist[id[1]]=mi[id[1]]; 如果只更正了错误1没更正错误2过不了下面这个样例，可以试一试

input
2 1
1 100
1 2 1
output
99

所以建议同时添加这两个样例，以验证错误1和错误2！