spfa算法模闆

//最短路之spfa算法模闆 
const int INF = 0x3f3f3f3f;
const int MAX_V = ???;
struct edge {	//cost代表一個點到to這個點的權值 
	int to, cost;
}; 
int V, M;			//頂點數,邊數 
vector<edge> G[MAX_V];	//G[i]存放的是第i個點到 其他點的序号和權值  
int d[MAX_V];	//d[i]存放的是指定節點s到i的最短距離 
bool vis[MAX_V];	//vis[i]标記第i個頂點是否在隊列 
int count ;
void spfa(int s) {
	count = 0;	//統計循環次數 
	queue<int > que;	//存頂點 
	fill(d, d+V, INF);		//初始化d
	fill(vis, vis+V, false);
	d[s] = 0;			
	que.push(s);	//把第一個點序号存入 
	while(!que.empty()) {
		int i, v = que.front(); que.pop();
		vis[v] = false;	//v不在隊列中 
		for(int i = 0;i < G[v].size();i ++){
			edge e = G[v][i]; 
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				if(++ count > V * M)	//判斷負圈 
					break;
				if(!vis[e.to]){	//如果e.to不在隊列中 
					que.push(e.to);
					vis[e.to] = true;
				}
			}
		}
	}
}
//注意：如果是多組資料記得周遊頂點用G[i].clear();來清空G[v]，否則會影響第二組資料
while(V --)	G[V].clear();
if(count > V * M)	no answer;