amoshyc/poj3169.md

## poj3169.md

      
    Raw
  

              poj3169.md
            
          
    Poj 3169: Layout

題目

分析

這就是所謂的 差分約束系統 啊，第一次寫到…
將多個同型式的不等式轉化成最短路徑問題，原理請參 這
之後照著做就是了
題外話，想不到 Edge{a, b, w} 這種寫法是 C++11 才有的，不過在 poj 上選 G++ 也可以用，
只是會產生 Warning 而已
AC Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v, cost;
};

Edge edges[10000 * 2 + 1];
int N, ML, MD;
int V, E;

int solve() {
    // bellman ford
    int d[V];
    memset(d, INF, sizeof(d));
    d[1] = 0;

    for (int i = 0; i < V; i++) {
        bool update = false;

        for (int j = 0; j < E; j++) {
            Edge& e = edges[j];
            if (d[e.v] > d[e.u] + e.cost) {
                d[e.v] = d[e.u] + e.cost;
                update = true;

                if (i == V-1)
                    return -1;
            }
        }

        if (!update)
            break;
    }

    if (d[N] == INF)
        return -2;
    return d[N];
}

int main() {
    scanf("%d %d %d", &N, &ML, &MD);

    int idx = 1;
    for (int i = 0; i < ML; i++) {
        int A, B, D;
        scanf("%d %d %d", &A, &B, &D);
        edges[idx++] = Edge{A, B, D};
    }
    for (int i = 0; i < MD; i++) {
        int A, B, D;
        scanf("%d %d %d", &A, &B, &D);
        edges[idx++] = Edge{B, A, -D};
    }
    // d[i+1] >= d[i]
    // d[i] - d[i+1] <= 0
    // d[i] <= d[i+1] + 0
    for (int i = 1; i < N; i++) {
        edges[idx++] = Edge{i+1, i, 0};
    }

    V = N + 1;
    E = idx;

    printf("%d\n", solve());

    return 0;
}