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

题目链接：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 0X3f3f3f3f
using 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;
}