测试3T3-差分约束路径

#include
#include
#include
#include
using namespace std;
#define INF 0x7FFFFFFF
#define N 500005
#define M 2000000
int dist[N],num=0,ans=0,a[N];
int n,m;
struct note{
    int u,v,c;
}Edge[M];
void debug()
{
    for(int i=0;i<=n;i++)
    cout<<"i="<" dist="<endl;
    cout<<"***********************\n"; 
}
void make_way(int u,int v,int z)
{
    Edge[++num].u=u,Edge[num].v=v,Edge[num].c=z;
}
void bellman_ford(){
    int f=1;  int t;
    while(f){
        f=0;
        for(int i=1;i<=m;i++)   if(dist[Edge[i].v]>(t=dist[Edge[i].u]+Edge[i].c))  dist[Edge[i].v]=t,f=1;
        for(int i=1;i<=n;i++)   if(dist[i]-dist[i-1]>a[i])  dist[i]=dist[i-1]+a[i],f=1;
        for(int i=n;i;i--)      if(dist[i-1]>dist[i]) dist[i-1]=dist[i],f=1;
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        //make_way(i-1,i,dist[i]),make_way(i,i-1,0);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        make_way(y,x-1,-z);
    }
    //debug();
    
    memset(dist,0,sizeof(dist));
    /*for(int i=1;i<=num;i++)
        printf("num:%d u:%d v:%d c:%d\n",i,Edge[i].u,Edge[i].v,Edge[i].c);
        cout<<-dist[0]<*/
    bellman_ford();    
    cout<0]<<endl;
     
}