拓扑50分：

由于数据中已明确写出有50%数据没有环.所以有50%数据可拓扑

以下为50分代码(挺好理解的就不贴图):

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int r[100001],minf[100001],maxf[1000001],a[100001],c[100001];

bool visa[100001],visb[100001];

vector<int> g[100001],gf[100001];

int main()
{
    //freopen("a.txt","r",stdin);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        minf[i]=a[i];
        maxf[i]=a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back(y);
        gf[y].push_back(x);
        r[y]++;
        c[x]++;
        if(z==2)
        {
            g[y].push_back(x);
            gf[x].push_back(y);
            c[y]++;
            r[x]++;
        }
    }
    queue<int> q;
    q.push(1);
    visa[1]=true;

    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        int l=g[t].size();
        for(int i=0;i<l;i++)
        {
            int ne=g[t][i];
            r[ne]--;
            visa[ne]=true;
            minf[ne]=min(minf[ne],minf[t]);
            if(r[ne]==0)
            {
                q.push(ne);
            }
        }
    }
    q.push(n);
    visb[n]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        int l=gf[t].size();
        for(int i=0;i<l;i++)
        {
            int ne=gf[t][i];
            c[ne]--;
            visb[ne]=true;
            maxf[ne]=max(maxf[ne],maxf[t]);
            if(c[ne]==0)
            {
                q.push(ne);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(visa[i] && visb[i])
            ans=max(ans,maxf[i]-minf[i]);
    }
    cout<<ans;
}

DFS/BFS+DFS/BFS+DFS/BFS 70-100分:

这个方法很神奇.三轮搜索

第一轮找到1能到的点

第二轮找到能到n的点

将数组求并集.

第三轮在并集中找到最大值

正常应该100分.(但我太菜了所以只拿了70分QwQ)

代码:

#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int a[50001];

vector<int> g[50001],gf[50001];

bool visa[50001],visb[50001],visc[50001];

int con=0;

struct edge
{
    int x;
    int z;
}vis[50001];

bool cmp(edge x,edge y)
{
    return x.z<y.z;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back(y);
        gf[y].push_back(x);
        if(z==2)
        {
            g[y].push_back(x);
            gf[x].push_back(y);
        }
    }
    queue<int> q;
    q.push(1);
    visa[1]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        int l=g[t].size();
        for(int i=0;i<l;i++)
        {
            int ne=g[t][i];
            if(!visa[ne])
            {
                visa[ne]=true;
                q.push(ne);
            }
        }
    }

    q.push(n);
    visb[n]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        int l=gf[t].size();
        for(int i=0;i<l;i++)
        {
            int ne=gf[t][i];
            if(!visb[ne])
            {
                visb[ne]=true;
                q.push(ne);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(visa[i] && visb[i])
        {
            con++;
            vis[con].x=i;
            vis[con].z=a[i];
        }
    }

    sort(vis+1,vis+1+con,cmp);
    int ans=0;
    for(int i=1;i<=con;i++)
    {
        memset(visc,0,sizeof(visc));
        q.push(vis[i].x);
        int tx=vis[i].z;
        visc[i]=true;
        while(!q.empty())
        {
            int t=q.front();
            q.pop();
            ans=max(ans,a[t]-tx);
            int l=g[t].size();
            for(int i=0;i<l;i++)
            {
                int ne=g[t][i];
                if(visb[ne] && !visc[ne])
                {
                    visc[ne]=true;
                    q.push(ne);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

SPFA算法 标准100分

这个思路比较明确

第v[i]点为从1到i一路上最小值

t[i]表示从i到n的最大值

代码如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int a[100001],tb[100001],ta[100001];

vector<int> g[100001],gf[100001];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back(y);
        gf[y].push_back(x);
        if(z==2)
        {
            g[y].push_back(x);
            gf[x].push_back(y);
        }
    }
    queue<int> q;
    q.push(1);
    memset(ta,127,sizeof(ta));
    ta[1]=2147483647;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        ta[t]=min(ta[t],a[t]);
        int l=g[t].size();
        for(int i=0;i<l;i++)
        {
            if(ta[t]<ta[g[t][i]])
            {
                ta[g[t][i]]=ta[t];
                q.push(g[t][i]);
            }
        }
    }
    q.push(n);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        tb[t]=max(tb[t],a[t]);
        int l=gf[t].size();
        for(int i=0;i<l;i++)
        {
            if(tb[t]>tb[gf[t][i]])
            {
                tb[gf[t][i]]=tb[t];
                q.push(gf[t][i]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,tb[i]-ta[i]);
    }
    cout<<ans;
    return 0;
}