学步园

题意：N头牛排队吃饭 排编号顺序排，大的永远在小的前面，但牛之间有的关系好，有的差，所以有的牛想离某些牛的距离最远不超过D
有的必须大于D 给出它们的关系 求第n头牛跟第一头的最远距离

思路：差分问题，求最大值 约束条件转化为 < ； 所以有S大-S小 <=
D1,
S大-S小>=D2 把这个条件转化一下==>
S小-S大<=-D2

然后就是spfa了

#include <stdio.h>
#include <string.h>
#define VM 10005
#define EM
200500   
//原先数据都是少一个0的，但RE 不知为什么 多加一个就过了
#define inf 9999999999
struct edge
{
    int
v,w,next;
}e[EM];
int head[VM],ep;
void addedge (int cu,int cv,int cw)
{
    ep ++;
    e[ep].v =
cv;
    e[ep].w =
cw;
    e[ep].next =
head[cu];
    head[cu] =
ep;
}

__int64 spfa (int n)
{
    int
vis[VM],cnt[VM],queue[VM];
    __int64
dis[VM];
    for (int i =
1;i <= n;i ++)
    {
       
vis[i] = 0;
       
cnt[i] = 0;
       
dis[i] = inf;
    }
    dis[1] =
0;
    int front =
-1,rear = 0;
    vis[1] =
1;
    cnt[1] =
1;
    queue[rear
++] = 1;
    while (front
!= rear)
    {
       
front = (front+1)%(n+1);
       
int u = queue[front];
       
vis[u] = 0;
       
for (int i = head[u];i != -1;i = e[i].next)
       
{
           
int v = e[i].v;
           
if (dis[v] > dis[u]+e[i].w)
           
{
               
dis[v] = dis[u] + e[i].w;
               
if (!vis[v])
               
{
                   
vis[v] = 1;
                   
cnt[v] ++;
                   
if (cnt[v] >= n)