题目链接:POJ3169-Layout
题意:
n头牛,有m1对友好关系,要求牛a与牛b的距离不超过c,有m2对敌对关系,要求牛a与牛b的距离不少于c,问牛1到牛n的最大距离。
题解:
有几个地方有点小坑。
- 题面数据n的范围是1000,m1和m2是10000,但是总是re,开大点就能过了。
- 注意建图是建立在数轴上的。
只需要建图然后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;
}