据说是最高效的邻接表....
别误会，小人只是个渣，这里不自量力下，昨天刚向老蔡学的，给出我的理解
先给出数据结构
struct EDGE
{
int next;
int to;
int dist;
}mat[3*maxn];
int head[maxn];
next 这个.........不好表达，先说下面的
to 很显然，给出一条边，to就是边的终点
dist 就是这条边的权值
好的，还是说下我对next的理解吧
实际上是这样的，一般题目都会让你输入一堆边，那么这些边里免不了会有由同个起点引出的边，显然我们的边肯定是按输入顺序写在结构体里的，那么比如先输入了 1 5 7，意思是从1到5有一条边，长度是7 ，再输入 1 6 4，意思是从1到6有一条边，长度是4，这样的话，对于后一条边，他的mat[num].next就要指向离他最近的(前一个)有着同起点的边的下标，比如 mat[1].to=5.mat[1].dist=7,mat[1].next=-1 那么 mat[2].to=6,mat[2].dist=4,mat[2].next=1;
呼~~果然不是省油的灯，所谓的精华版邻接表
擦，还有个head数组没讲~~~~→→
head 数组，是用来指向最新的有着同起点的那条边的下标
比如前面的例子，那么起先全部初始化为-1（不是-1也可以，只要不会与你要用的重复就好了） ，head[1]先等于1，因为这是第一条边，也是最新的一条，但是接下来，head[1]要更新为2；
终于把这个解释好了
不过昨天有小伙伴问我，起点是怎么存的
我来说明下，head数组的下标就是你的起点，正因为有了这个数组，所以我们不需要关注起点，他可以飞快的帮我们找到
为了方便理解，我放点图上去
| 起点 |
终点 |
边权 |
| 1 |
3 |
7 |
| 2 |
3 |
6 |
| 1 |
4 |
5 |
| 3 |
5 |
1 |
| 2 |
7 |
11 |
| 4 |
5 |
7 |
| 3 |
4 |
6 |
| 2 |
4 |
5 |
| 1 |
2 |
7 |
| 下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| to |
3 |
3 |
4 |
5 |
7 |
5 |
4 |
4 |
2 |
| dist |
7 |
6 |
5 |
1 |
11 |
7 |
6 |
5 |
7 |
| next |
-1 |
-1 |
1 |
-1 |
2 |
-1 |
4 |
5 |
3 |
| 下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| head |
1->3->9 |
2->5->8 |
4->7 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
实际上head只需要根据点的数量来选择数组的大小
一般mat数组的大小为head的3-4倍
哦~对了，那么上述过程如何实现呢，附上一小段代码
struct EDGE
{
int next;
int to;
int dist;
}mat[3*maxn];
int head[maxn];
int edgenum;
void addedge(int s,int t,int dis)
{
mat[edgenum].to=t;
mat[edgenum].dist=dis;
mat[edgenum].next=head[s]; //这条和下一条的代码千万不能反，否则就连不起来了
head[s]=edgenum++;
}
~~~~~屌丝飘过