数组模拟邻接表很高效,代码实现如下:

struct EDGE
{
	int next;//下一条边的编号 
	int to;//这条边指向的点 
	int co;//这条边的花费 
}edge[maxn*4];
void add(int from,int to,int co)//建一个从from到to,代价co的边 
{
	edge[++qr].next=head[from];//新边指向旧边,倒着连边 
	edge[qr].to=to;
	edge[qr].co=co;
	head[from]=qr;//更新下一次要用到的旧边(目前的边) 
}

难解之处:倒着连边,再倒着找边

分类:

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注