poj3411 Paid Roads
IAmL
posted @ 2009年5月01日 20:53
in 解题报告
with tags
poj3411 Paid Roads
, 2584 阅读
最近rp真是出了点问题。身边发生了许多不顺心的事情。现在连做一道题都用了那么久时间。
首先说说题目大意：有一些点，然后有些点有边，每条边有两个权值，一个是普通的权值，一个是必须经过某些点后才能用的权值。
然后思路：其实这题就是搜索题。关键是状态的定义：f[i][j]表示从1到 j状态为i的最少费用。其实已经做过几题类型的，但是想状态的时候还是用了不少时间。看来对于知识的迁移还是不够，对增加维度来减少问题复杂度这个思想还是不是很熟悉。
＝＝＝＝＝＝＝＝＝＝＝＝＝分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
注：代码中对结点的两种扩展是有必要的，不能只判断是否符合用特殊条件的权值，而要把普通权值也放进来考虑。这样做的原因可以从我们对状态的定义得出。
#include <iostream>
using namespace std;
#define Max 1000000
#define Size 1000
int n, m, minimum = Max, f[(1 << 10)][11];
//邻接表的结点
struct Lnode
{
int p, r, c, b;
Lnode *next;
Lnode(){next = NULL;}
};
struct list
{
Lnode *next;
list():next(NULL){}
}g[11];
//队列的结点b表示当前所在结点，len表示当前费用，state表示当前状态
struct Qnode
{
int b, len, state;
Qnode():state(0){}
}p, q[Size];
void BFS()
{
int head, tail;
Lnode *pp;
//initialize
memset(f, -1, sizeof(f));
head = tail = 0;
p.len = 0;
p.state = 1;
p.b = 0;
f[1][0] = 0;
q[tail++] = p;
while (head < tail)
{
p = q[head++];
pp = g[p.b].next;
while (pp != NULL)
{
q[tail].b = pp->b;
q[tail].len = pp->r + p.len;
q[tail].state = p.state | (1 << pp->b);
if (f[q[tail].state][q[tail].b] == -1 || f[q[tail].state][q[tail].b] > q[tail].len)
{
f[q[tail].state][q[tail].b] = q[tail].len;
tail++;
}
if (p.state & (1 << pp->c))
{
q[tail].b = pp->b;
q[tail].len = pp->p + p.len;
q[tail].state = p.state | (1 << pp->b);
if (f[q[tail].state][q[tail].b] == -1 || f[q[tail].state][q[tail].b] > q[tail].len)
{
f[q[tail].state][q[tail].b] = q[tail].len;
tail++;
}
}
pp = pp->next;
}
}
}
void output()
{
int i, size = (1 << 10);
for (i = 0; i < size; i++)
if (f[i][n] >= 0 && f[i][n] < minimum) minimum = f[i][n];
if (minimum < Max) cout << minimum << endl;
else cout << "impossible\n";
}
int main()
{
int i, a, b, c, p, r;
Lnode *pp;
scanf("%d%d", &n, &m);
n--;
//insert
for (i = 0; i < m; i++)
{
scanf("%d%d%d%d%d", &a, &b, &c, &p, &r);
a--;
b--;
c--;
pp = new Lnode;
pp->b = b;
pp->c = c;
pp->p = p;
pp->r = r;
pp->next = g[a].next;
g[a].next = pp;
}
//solve
BFS();
output();
return 0;
}
using namespace std;
#define Max 1000000
#define Size 1000
int n, m, minimum = Max, f[(1 << 10)][11];
//邻接表的结点
struct Lnode
{
int p, r, c, b;
Lnode *next;
Lnode(){next = NULL;}
};
struct list
{
Lnode *next;
list():next(NULL){}
}g[11];
//队列的结点b表示当前所在结点，len表示当前费用，state表示当前状态
struct Qnode
{
int b, len, state;
Qnode():state(0){}
}p, q[Size];
void BFS()
{
int head, tail;
Lnode *pp;
//initialize
memset(f, -1, sizeof(f));
head = tail = 0;
p.len = 0;
p.state = 1;
p.b = 0;
f[1][0] = 0;
q[tail++] = p;
while (head < tail)
{
p = q[head++];
pp = g[p.b].next;
while (pp != NULL)
{
q[tail].b = pp->b;
q[tail].len = pp->r + p.len;
q[tail].state = p.state | (1 << pp->b);
if (f[q[tail].state][q[tail].b] == -1 || f[q[tail].state][q[tail].b] > q[tail].len)
{
f[q[tail].state][q[tail].b] = q[tail].len;
tail++;
}
if (p.state & (1 << pp->c))
{
q[tail].b = pp->b;
q[tail].len = pp->p + p.len;
q[tail].state = p.state | (1 << pp->b);
if (f[q[tail].state][q[tail].b] == -1 || f[q[tail].state][q[tail].b] > q[tail].len)
{
f[q[tail].state][q[tail].b] = q[tail].len;
tail++;
}
}
pp = pp->next;
}
}
}
void output()
{
int i, size = (1 << 10);
for (i = 0; i < size; i++)
if (f[i][n] >= 0 && f[i][n] < minimum) minimum = f[i][n];
if (minimum < Max) cout << minimum << endl;
else cout << "impossible\n";
}
int main()
{
int i, a, b, c, p, r;
Lnode *pp;
scanf("%d%d", &n, &m);
n--;
//insert
for (i = 0; i < m; i++)
{
scanf("%d%d%d%d%d", &a, &b, &c, &p, &r);
a--;
b--;
c--;
pp = new Lnode;
pp->b = b;
pp->c = c;
pp->p = p;
pp->r = r;
pp->next = g[a].next;
g[a].next = pp;
}
//solve
BFS();
output();
return 0;
}
评论 (0)