题目链接：http://poj.org/problem?id=3159

题意：给n个人派糖果，给出m组数据，每组数据包含A，B，c 三个数，意思是A的糖果数比B少的个数不多于c,即B的糖果数 - A的糖果数<= c 。

最后求n比1最多多多少糖果。

可以从条件中的

B-A<=c及B<=A+c最后要达成这个条件就是要当B>A+c时B=A+c即可

所以差不多就是求最短路。这题中还有一些优化比如

if(vis[u]) continue;这个避免了u点的重复查找

#include <iostream>#include <string>#include <cstring>#include <vector>#include <queue>#include <cstdio>#define inf 0X3f3f3f3fusing namespace std;const int M = 2e5;int n , m , a , b , c , dis[30010];struct TnT {    int u , v , w , next;}T[M];struct qnode{    int v , c;    qnode(int v , int c):v(v) , c(c){}    bool operator < (const qnode &r) const{        return c > r.c;    }};int head[30010] , e;void add(int u , int v , int w) {    T[e].v = v;    T[e].w = w;    T[e].next = head[u];    head[u] = e++;}bool vis[M];void dij(int s) {    priority_queue<qnode>q;    memset(vis , false , sizeof(vis));    q.push(qnode(s , 0));    dis[s] = 0;    while(!q.empty()) {        int u = q.top().v;        q.pop();        if(vis[u])            continue;        vis[u] = true;        for(int i = head[u] ; i != -1 ; i = T[i].next)  {            int v = T[i].v , w = T[i].w;            if(!vis[v] && dis[v] > dis[u] + w) {                dis[v] = dis[u] + w;                q.push(qnode(v , dis[v]));            }        }    }}int main() {    while(scanf("%d%d" , &n , &m) != EOF) {        e = 0;        for(int i = 1 ; i <= n ; i++) {            dis[i] = inf;            head[i] = -1;        }        for(int i = 1 ; i <= m ; i++) {            scanf("%d%d%d" , &a , &b , &c);            add(a , b , c);        }        dij(1);        printf("%d\n" , dis[n]);    }    return 0;}

poj 3159 Candies（dijstra优化非vector写法）