题目链接：POJ3169-Layout

题意：

n头牛，有m1对友好关系，要求牛a与牛b的距离不超过c，有m2对敌对关系，要求牛a与牛b的距离不少于c，问牛1到牛n的最大距离。

题解：

有几个地方有点小坑。

1. 题面数据n的范围是1000，m1和m2是10000，但是总是re，开大点就能过了。
2. 注意建图是建立在数轴上的。

只需要建图然后spfa即可。

对于友好关系，建边(a,b)=w，对于敌对关系，建边(b,a)=-w即可。

参考代码：

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 10003;
const int MAXM = 200005;
const int inf = 0x3f3f3f3f;
int n, m1, m2;
int dis[MAXN], used[MAXN], CNT[MAXN];
struct EDGE
{
    int v, w, nxt;
} edge[MAXN];
int cnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
bool spfa(int st)
{
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    memset(used, 0, sizeof(used));
    memset(CNT, 0, sizeof(CNT)); //记录从起点到 i 点的最短距离包含点的个数
    dis[st] = 0;
    queue<int> que;
    while (!que.empty())
        que.pop();
    que.push(st);
    while (!que.empty())
    {
        int u = que.front();
        used[u] = 0;
        que.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                CNT[v] = CNT[u] + 1;
                if (CNT[v] > n)
                    return 0; //存在负环
                if (!used[v])
                {
                    que.push(v);
                    used[v] = 1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d%d", &n, &m1, &m2);
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= m1; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
    }
    for (int i = 1; i <= m2; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(v, u, -w);
    }
    if (!spfa(1))
        puts("-1");
    else
    {
        if (dis[n] == inf)
            puts("-2");
        else
            printf("%d\n", dis[n]);
    }
    return 0;
}