Candies

差分约束系统

这是我第一次接触到差分约束系统。还行

a b c代表d[b]<=d[a]+c
是否？
我们就见一条边a->b代表d[b]<=d[a]+c
那么我们求解d[1]与d[n]的最大区分则
假设1到n之间有这样的条路经：e1,e2,e3......
那么d[n]<=d[1]+e1+e2+e3......
这个不等式要对所有的路径都成立。
那么，自然要对和最小的哪一个路径成立啦
即，最终答案就是最短路径

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<functional>
using namespace std;
typedef pair<int, int> pii;
const int max_m = 15e4 + 100;
const int max_n = 3e4 + 100;
struct edge{
    int to, cost, next;
}E[max_m];
int head[max_n];
int cnt = 1;
void add(int from, int to,int cost) {
    E[cnt].to = to;E[cnt].cost = cost;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
int d[max_n];
int dij(int s,int t) {
    fill(d, d + max_n, 2e9);d[s] = 0;
    priority_queue<pii,vector<pii>,greater<pii> > que;
    que.push(pii(d[s], s));
    while (!que.empty()) {
        pii p = que.top();
        que.pop();
        int u = p.second;int dist = p.first;
        if (dist > d[u])continue;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost;
                que.push(pii(d[e.to], e.to));
            }
        }
    }return d[t];
}

int N, M;
int main() {
    while (scanf("%d %d", &N, &M) != EOF) {
        fill(head, head + max_n, 0);cnt = 1;
        for (int i = 1, u, v, c;i <= M;++i) {
            scanf("%d %d %d", &u, &v, &c);
            add(u, v, c);
        }printf("%d\n", dij(1, N));
    }
}