题目大意：给你一张有n个点m条边的有向图，每个点有一个权值，求一条1到n的路径，使得这条路径上存在两个点且他们的权值差最大。

思路：用dis[i]]记录从1到i的路径中所能得到两点间权值差的最大值，然后用spfa或dijkstra来求dis数组的最大值

#include
     
      #include
      
       #include
       
        #include
        
         const int MAXN=200007; using namespace std;queue
         
           q;int head[MAXN],nextt[MAXN],dis[MAXN],tot,e[2000077],buy[MAXN];int vis[MAXN];template
          
           void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x;}void add(int u,int v){ e[++tot]=v; nextt[tot]=head[u]; head[u]=tot;}int main(){ int x,y,z,m,n; memset(dis,-1,sizeof(dis)); read(n),read(m); for(int i=1;i<=n;++i) read(buy[i]); for(int i=1;i<=m;++i) { read(x),read(y),read(z); add(x,y); if(z==2) add(y,x); } q.push(1); while(!q.empty()) { int x=q.front();q.pop(); vis[x]=233; for(int i=head[x];i;i=nextt[i]) { int y=e[i]; if(dis[y]==-1||dis[y]
           
            0) dis[y]=buy[y]-buy[x]; } if(dis[y]
            
             dis[y]) dis[y]=dis[x]; } if(vis[y]==0) { vis[y]=1; q.push(y); } } } if(dis[n]==-1) printf("0"); else printf("%d",dis[n]); return 0;}