P1073 最优贸易

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<vector>
  7 #include<map>
  8 using namespace std;
  9 const int ma1=100010,ma2=500010,maxn=2147483647;
 10 typedef pair<int ,int > node;
 11 struct Edge
 12 {
 13     int next,to;
 14 } E1[ma2],E2[ma2];
 15 int V[ma1];
 16 int num_Edge1,Head1[ma1],Min[ma1],vis1[ma1];
 17 int Max[ma1],num_Edge2,Head2[ma1],vis2[ma1];
 18 int N,M,Ans;
 19 map<pair<int,int>,bool>Map;
 20 inline int Read(void)
 21 {
 22     int w=0,x=0;
 23     char ch=0;
 24     while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar();
 25     while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
 26     return w?-x:x;
 27 }
 28 void Add_Edge1(int from,int to)
 29 {
 30     ++num_Edge1;
 31     E1[num_Edge1].next =Head1[from];
 32     E1[num_Edge1].to =to;
 33     Head1[from]=num_Edge1;
 34 }
 35 void Add_Edge2(int from,int to)
 36 {
 37     ++num_Edge2;
 38     E2[num_Edge2].next =Head2[from];
 39     E2[num_Edge2].to =to;
 40     Head2[from]=num_Edge2;
 41 }
 42 inline void SPFA1(void)// 寻找路径上最小价格点(从源点出发)
 43 {
 44     queue<int >Q1;
 45     Min[1]=V[1];
 46     Q1.push(1) ;
 47     while(!Q1.empty() )
 48     {
 49         int u=Q1.front();
 50         Q1.pop() ;
 51         vis1[u]=0; //出队标记
 52         for(int i=Head1[u]; i; i=E1[i].next )
 53         {
 54             int v=E1[i].to ,t=min(Min[u],V[v]);
 55             if(Min[v]>t)
 56             {
 57                 Min[v]=t;
 58                 if(!vis1[v])
 59                 {
 60                     vis1[v]=1;
 61                     Q1.push(v) ;
 62                 }
 63             }
 64         }
 65     }
 66 }
 67 inline void SPFA2(void)//寻找从N点出发所能到达的最大价格处
 68 {
 69     queue<int >Q2;
 70     Q2.push(N) ;
 71     while(!Q2.empty() )
 72     {
 73         int u=Q2.front();
 74         Q2.pop() ;
 75         vis2[u]=0; //出队标记
 76         for(int i=Head2[u]; i; i=E2[i].next )
 77         {
 78             int v=E2[i].to ,t=max(Max[u],V[v]);
 79             if(Max[v]<t)
 80             {
 81                 Max[v]=t;
 82                 if(!vis2[v])
 83                 {
 84                     vis2[v]=1;
 85                     Q2.push(v) ;
 86                 }
 87             }
 88         }
 89     }
 90 }
 91 inline void Write()
 92 {
 93     N=Read(),M=Read() ;
 94     for(int i=1; i<=N; ++i) Min[i]=maxn;
 95     for(int i=1; i<=N; ++i) V[i]=Read();
 96     for(int i=1; i<=M; ++i)   //建图
 97     {
 98         int u=Read(),v=Read(),m=Read();
 99         if(m==1)
100         {
101             Add_Edge1(u,v);//正图 
102             Add_Edge2(v,u);//反图
103         }
104         else
105         {
106             Add_Edge1(v,u);//正图
107             Add_Edge1(u,v);
108             Add_Edge2(v,u);//反图
109             Add_Edge2(u,v);
110         }
111     }
112 }
113 int main(void)
114 {
115     Write();
116     SPFA1();
117     SPFA2();
118     for(int i=1; i<=N; ++i)//计算最大差值 
119     {
120         if(Min[i]!=maxn&&Max[i]!=0)//保证此点在从1到N的路径上 
121             Ans=max(Max[i]-Min[i],Ans);
122     }
123     printf("%d",Ans);
124     return 0;
125 }