POJ 3169 Layout——差分约束

POJ 3169 Layout——差分约束

​

#include #include #include #include #include using namespace std;const int MAXN = 1010;const int MAXM = 200010;const int INF = 0x3f3f3f3f;bool vis[MAXN];int N, ML, MD, tot, head[MAXN], num[MAXN], dis[MAXN];struct Edge { int to, cost, next;}edge[MAXM];void Init() { tot = 0; for (int i = 1; i <= N; i++) head[i] = -1;}void AddEdge(int u, int v, int cost) { tot++; edge[tot].to = v; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot;}int spfa() { for (int i = 1; i <= N; i++) dis[i] = INF, vis[i] = false, num[i] = 0; dis[1] = 0, num[1]++; queue q; q.push(1); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] =false; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (dis[v] > dis[u] + cost) { dis[v] = dis[u] + cost; if (!vis[v]) { vis[v] = true; num[v]++; q.push(v); if (num[v] > N) { return -1; } } } } } return dis[N] == INF ? -2 : dis[N];}int main() { while (~scanf("%d %d %d", &N, &ML, &MD)) { Init(); for (int i = 1; i <= ML; i++) { int u, v, cost; scanf("%d %d %d", &u, &v, &cost); AddEdge(u, v, cost); } for (int i = 1; i <= MD; i++) { int u, v, cost; scanf("%d %d %d", &u, &v, &cost); AddEdge(v, u, -cost); } printf("%d\n", spfa()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。