homework32.cpp~

 #include <iostream>
#include <queue>
using namespace std;

const int MAXN = 1000;
const int MAXM = 100000;
const int INF = 100000000;
int n, m;
int first[MAXN], d[MAXN], done[MAXN]; //在寻找距离源点最近的点x过程中，done[i]表示第i个节点已经被处理过
int u[MAXM], v[MAXM], w[MAXM], ne[MAXM];
typedef pair<int, int> pii;

int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) first[i] = -1; //初始化邻接表的表头 
	for(int e = 0; e < m; ++e) { //邻接表的建立 
		cin >> u[e] >> v[e] >> w[e];
		ne[e] = first[u[e]];
		first[u[e]] = e;
	}
	priority_queue< pii, vector<pii>, greater<pii> > q; //用于在所有未处理过的节点中，选出d值最小的节点x
	memset(done, 0, sizeof(done)); //一开始假设所有节点都没有被处理过 
	q.push(make_pair(d[0], 0)); //起点进入优先队列 
	for(int i = 0; i < n; ++i) d[i] = (i == 0 ? 0 : INF);
	while(!q.empty()) {
		pii u = q.top();
		q.pop();
		int x = u.second; //x表示当前d值最小的节点的节点号 
		if(done[x]) continue; //已经算过，忽略 
		done[x] = 1;
		for(int e = first[x]; e != -1; e = ne[e]) { //遍历从x出发的所有边（x,y）更新d[y]
			if(d[v[e]] > d[x] + w[e]) {
				d[v[e]] = d[x] + w[e]; //松弛成功，更新d[v[e]]
				q.push(make_pair(d[v[e]], v[e]));
			}
		}
	}
	for(int i = 0; i < n; ++i) cout << d[i] << endl; 
	return 0;
}