简单的一个模板吧，留个底。如果要判负环的话，需要加一个cnt数组记录入队次数就可以了。

void spfa(int st) {
	memset(dis,INF,sizeof dis);
	queue<int> q;q.push(st);
	dis[st]=0;vis[st]=1;
	while(!q.empty()) {
		int cur = q.front();q.pop();vis[cur]=0;
		int up = vv[cur].size();
		for(int i = 0; i<up; i++) {
			Edge now = vv[cur][i];
			int to = now.to;
			if(dis[to] > dis[cur] + now.w) {
				dis[to] = dis[cur]+now.w;
				if(vis[to] == 0) vis[to]=1,q.push(to);
			}
		}
	}
}

单源最短路条数：

void spfa(int st) {
	memset(dis,INF,sizeof dis);
	queue<int> q;q.push(st);
	dis[st]=0;vis[st]=1;
	while(!q.empty()) {
		int cur = q.front();q.pop();vis[cur]=0;
		int up = vv[cur].size();
		for(int i = 0; i<up; i++) {
			Edge now = vv[cur][i];
			int to = now.to;
			if(dis[to] > dis[cur] + now.w) {
				dis[to] = dis[cur]+now.w;
				dp[to] = dp[cur];
				if(vis[to] == 0) vis[to]=1,q.push(to);
			}
			else if(dis[to] == dis[cur] + now.w) {
				dp[to] += dp[cur];
			}
		}
	}
}