vector

说实话，我也没有搞的太清楚它是干什么的。不过做题的时候，似乎只要知道可以写邻接矩阵，挺好用的。

之前邻接矩阵需要这么写：

int a[1005][1005];

然后遍历的时候这样：

for (int i=0;i<n;i++)

    for (int j=0;j<m;j++)

    a[i][j]=...

这样的坏处是最多存10000的宽度，到100000数据肯定不行

 

因此有了这个玩意来救我们。本质上是一个稀疏矩阵，把东西压缩一下就能用了

struct P

{int to;int cost}

vector <P>e[100005];

然后输入是这样

//假设输入是起点，终点，权值

for (int i=0;i<m;i++)
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c)
    P temp;
    temp.to=b;temp.cost=c;
    e[a].push_back(temp);
    temp.to=a;
    e[b].push_back(temp);
}

使用的时候，可以写e[i][j]，但是注意，这里的i代表着起点，但是j不代表终点，只代表一个存储顺序。最终需要知道终点需要先

edge temp=e[i][j];