存图的两种特殊方式

链式前向星

int e[N],ne[N],h[N],w[N],idx;
void add(int a,int b,int c){
    e[idx]=b;//e[]数组存数边的终点
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;//记录以t为出发点对应的第几条边
}

int main(){
    memset(h,-1,sizeof(h));
    //遍历以t为出发点的所有线路
    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];//t->j
        if(dist[j]>dist[t]+w[i]){
            dist[j]>dist[t]+w[i]
            ...
        }
    }
}

vector存图

vector<int>g[N];
for(int i=1;i<=m;i++){
    int a=read(),b=read();
    g[a].push_back(b);
}
//遍历
for(auto &i:g[t]){
    //t->i//这条边
}