当前位置: 首页 > >

POJ 3159 Candies 【差分约束系统 dijkstra+heap/spfa+stack】

发布时间:

POJ 3159 Candies

题目链接:vjudge传送门


题目大意:
给n个人分糖果,m组数据a,b,c;意思是a比b少的糖果个数绝对不超过c个,也就是d(b)-d(a) < c,求1比n少的糖果数的最大值。


具体思路:
差分约束系统第一次接触,我也不太懂,见博客
据说spfa+queue会超时,看好多人都用spfa+stack优化【第一次知道能用stack优化,但是我仍不知两者的差别】
故贴出dijkstra+优先队列的代码



其中关于优先队列的元素间的比较,用自定义比较结构体,重载(),一直wa,最后才用的重载<号运算符,至今不知为何错误。重载()慎用,最后我发现了pair有默认的比较函数,默认,比较first,first相同则比较second,对于dij+优先队列很方便code



具体代码:


//重载< ac code
#include
#include
#include
#include
using namespace std;
const int N = 3e4 + 5, M = 15e4 + 5;
struct Node {
int v, w, next;
}edg[M];
int visit[N];
int h[N];
int d[N];
int n, m;
int cnt = 1;

struct cmp {
int v, d;
cmp(int d, int v) : d(d), v(v) {}
bool operator < (const cmp &w) const {
return d > w.d;
}
};

void add(int u, int v, int w)
{
edg[cnt].v = v;
edg[cnt].w = w;
edg[cnt].next = h[u];
h[u] = cnt++;
}
void dijkstra()
{
memset(d, 0x3f, sizeof(d));
d[1] = 0;
priority_queue q;
q.push(cmp(0, 1));
while (q.size())
{
int t = q.top().v;
q.pop();
if (visit[t])continue;
visit[t] = 1;
for (int i = h[t]; i; i = edg[i].next)
{
int v = edg[i].v;
int w = edg[i].w;
if (d[v] > d[t] + w) {
d[v] = d[t] + w;
q.push(cmp(d[v], v));
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v, w; //u-v<=w
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
dijkstra();
printf("%d", d[n]);
return 0;
}

//pair ac code
#include
#include
#include
#include
using namespace std;
typedef pair P;
const int N = 3e4 + 5, M = 15e4 + 5;
struct Node {
int v, w, next;
}edg[M];
int visit[N];
int h[N];
int d[N];
int n, m;
int cnt = 1;
void add(int u, int v, int w)
{
edg[cnt].v = v;
edg[cnt].w = w;
edg[cnt].next = h[u];
h[u] = cnt++;
}
void dijkstra()
{
memset(d, 0x3f, sizeof(d));
d[1] = 0;
priority_queue, greater

> q;
q.push(P (0,1));
while (q.size())
{
int t = q.top().second;
q.pop();
if (visit[t])continue;
visit[t] = 1;
for (int i = h[t]; i; i = edg[i].next)
{
int v = edg[i].v;
int w = edg[i].w;
if (d[v] > d[t] + w) {
d[v] = d[t] + w;
q.push(P(d[v], v));
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v, w; //u-v<=w
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
dijkstra();
printf("%d", d[n]);
return 0;
}

分割线



贴一下一直wa的代码,留个坑


//WA code
#include
#include
#include
#include
using namespace std;
const int N = 3e4 + 5, M = 15e4 + 5;
struct Node {
int v, w, next;
}edg[M];
int visit[N];
int h[N];
int d[N];
int n, m;
int cnt = 1;
struct cmp {
bool operator()(int a, int b)
{
return d[a] > d[b];
}
};
void add(int u, int v, int w)
{
edg[cnt].v = v;
edg[cnt].w = w;
edg[cnt].next = h[u];
h[u] = cnt++;
}
void dijkstra()
{
memset(d, 0x3f, sizeof(d));
d[1] = 0;
priority_queue, cmp> q;
q.push(1);
while (q.size())
{
int t = q.top();
q.pop();
if (visit[t])continue;
visit[t] = 1;
for (int i = h[t]; i; i = edg[i].next)
{
int v = edg[i].v;
int w = edg[i].w;
if (d[v] > d[t] + w) {
d[v] = d[t] + w;
q.push(v);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v, w; //u-v<=w
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
dijkstra();
printf("%d", d[n]);
return 0;
}



友情链接: