记录编号	96132	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.388 s
提交时间	2014-04-10 22:35:11	内存使用	3.08 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <functional>
#define min minp
#define max maxs
using namespace std;
struct edges
{
  int to;
  edges *next;
}*head[100001],*rehead[100001];
struct ct
{
  int pre;
  int n;
};
int price[100001];
int min[100001];
int out[100001],reout[100001];
int max[100001];
bool inqueue[100001];
void addedge(int f,int t);
int main()
{
  freopen("trade.in","r",stdin);
  freopen("trade.out","w",stdout);
  int city,road;
  scanf("%d%d",&city,&road);
  for(int a=1;a<=city;a++)
  {
    scanf("%d",&price[a]);
    head[a]=new edges;
    rehead[a]=new edges;
    min[a]=101;
  }
  int f,t,w;
  memset(out,0,sizeof(out));
  memset(reout,0,sizeof(reout));
  for(int a=1;a<=road;a++)
  {
    scanf("%d%d%d",&f,&t,&w);
    addedge(f,t);
    if (w==2)
      addedge(t,f);
  }
  queue <int> Q;
  Q.push(1);
  memset(inqueue,false,sizeof(inqueue));
  while (!Q.empty())
  {
    int now=Q.front();
    Q.pop();
    inqueue[now]=false;
    edges *p=head[now];
    for(int k=1;k<=out[now];k++)
    {
      p=p->next;
      if (!inqueue[p->to]&&(min[p->to]>min[now]||min[p->to]>price[p->to]))
      {
        if (min[p->to]>min[now])
          min[p->to]=min[now];
        if (min[p->to]>price[p->to])
          min[p->to]=price[p->to];
        inqueue[p->to]=true;
        Q.push(p->to);
      }
    }
  }
  Q.push(city);
  memset(inqueue,false,sizeof(false));
  memset(max,0,sizeof(max));
  int earn=0;
  while (!Q.empty())
  {
    int now=Q.front();
    if (max[now]-min[now]>earn)
      earn=max[now]-min[now];
    Q.pop();
    inqueue[now]=false;
    edges *p=rehead[now];
    for(int a=1;a<=reout[now];a++)
    {
      p=p->next;
      if (!inqueue[p->to]&&(max[p->to]<max[now]||max[p->to]<price[p->to]))
      {
        if (max[p->to]<max[now])
          max[p->to]=max[now];
        if (max[p->to]<price[p->to])
          max[p->to]=price[p->to];
        inqueue[p->to]=true;
        Q.push(p->to);
      }
    }
  }
  cout<<earn;
  return 0;
}
//================================================
void addedge(int f,int t)
{
   reout[t]++;
   out[f]++;
   edges *p=new edges;
   p->to=t;
   p->next=NULL;
   if (head[f]->next==NULL)
      head[f]->next=p;
   else
   {
     p->next=head[f]->next;
     head[f]->next=p;
   }
   p=new edges;
   p->to=f;
   p->next=NULL;
   if (rehead[t]->next==NULL)
     rehead[t]->next=p;
   else
   {
     p->next=rehead[t]->next;
     rehead[t]->next=p;
   }
}