题意：已知一个序列a[1], a[2], ......, a[n]，给出它的若干子序列以及对该子序列的约束条件，例如a[si], a[si+1], a[si+2], ......, a[si+ni]，且a[si]＋a[si+1]＋a[si+2]＋......＋a[si+ni] < or > ki。

转化：a[a] + a[a+1] + …… + a[b] < c 可以转化成前n项和sum[b] - sum[a - 1] < c，为了能用Bellman_Ford,即将< 转化成 <= ，sum[b] - sum[a - 1] <= c - 1。

注意：1，松弛时一共有N+1次，因为这个N与bellman——ford里面的n不是同一个，在虚拟加入了一个x0后，应该有N+1个顶点。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7  8 struct Edge 9 {10     int s,e;11     int val;12 }edge[210];13 14 int pe;15 int N,M;16 int dis[110];17 18 bool bellman_ford()19 {20     bool sign;21 22     for(int j=0;j
          
            dis[edge[i].s] + edge[i].val)27             {28                 dis[edge[i].e] = dis[edge[i].s] + edge[i].val;29                 sign=true;30             }31         if(!sign)32             break;33     }34     if(sign)35         return false;//存在负环36     else37         return true;38 }39 40 int main()41 {42     while(scanf("%d",&N) && N)43     {44         scanf("%d",&M);45         memset(dis,0,sizeof(dis));//虚拟出一个x0，xi-x0<=046         pe=0;47 48         char op[3];49         int a,b,x;50 51         for(int i=0;i