数组模拟邻接表很高效,代码实现如下:
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;//更新下一次要用到的旧边(目前的边) }
难解之处:倒着连边,再倒着找边
欢迎来到睿屿青衫