一些有关图论的模板。

memset(d,0x3f,sizeof(d));
priority_queue< pair<int,int> > q;
q.push(make_pair(0,s));
d[s]=0; 
while(!q.empty){
	int u=q.top().second;
    q.pop();
    if(f[u]) continue;
    f[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(d[v]>d[u]+e[i].w){
			d[v]=d[u]+e[i].w;
			if(!f[v]) q.push(make_pair(-d[v],v));
		}
	}
}

memset(d,0x3f,sizeof(d));
d[s]=0,f[s]=1;
queue<int> q;
q.push(s);
while(!q.empty()){
	int u=q.front();
	q.pop(),f[u]=0;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(d[v]>d[u]+e[i].w){
			d[v]=d[u]+e[i].w;
			if(!f[v]){
				q.push(v);
				f[v]=1;
			}
		}
	}
}

int cnt,scc,dfn[],low[],f[],col[];
stack<int> s;
void Tarjan(int u){
	dfn[u]=low[u]=++cnt;
	s.push(u),f[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(f[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		scc++;
		int x=-1;
		while(x!=u){
			x=s.top();
			s.pop();
			f[x]=0;
			col[x]=u;
		}
	}
}

int cnt,dfn[],low[],root,c[]; 
void Tarjan(int u,int fr){
	dfn[u]=low[u]=++cnt;
	int tmp=0;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(!dfn[v]){
			tmp++;
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if((u==root && tmp>1) || (u!=root && dfn[u]<=low[v])){
				if(!c[u]) c[0]++;
				c[u]=1;
			}
		}else if(v!=fr){
			low[u]=min(low[u],dfn[v]);
		}
	}
}

int cnt,dfn[],low[];
vector<int> b[];
void Tarjan(int u,int fr){
	dfn[u]=low[u]=++cnt;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(!dfn[v]){
			tmp++;
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]){
				if(u<v) b[u].push_back(v);
				else b[v].push_back(u);
			} 
		}else if(v!=fr){
			low[u]=min(low[u],dfn[v]);
		}
	}
}