附上详解博客
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
代码是学长敲的，我在不懂的地方加了许多注释，我感觉这一周的东西学的特别吃力，都是一知半解，怀疑智商中。
/* n个点，m条边，求1 - n 的距离 输入x y z，表示x到y的距离为z 不存在输出-1 */ #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; #define INF 0x3f3f3f3f struct Pair { int first; //first存点 int second; //second存距离 bool friend operator < (Pair a,Pair b) //结构体是不能直接进行比较的,小于号的含义就是 { //如果a的second比b的second大，那么a就比b小 return a.second > b.second; //放到优先队列里，就是a的优先级小 } }a1,a2; int n,m; vector<int> edge[105]; //存与之相连的边 int length[105][105]; //存相连边的长度 int dis[105]; //记录到起点的距离 void dijkstra() { memset(dis,INF,sizeof(dis)); //把所有点到起点胡距离初始化为最大值 bool vis[105]; memset(vis,false,sizeof(vis)); dis[1] = 0; a1.first = 1; a1.second = 0; priority_queue<Pair> Q; Q.push(a1); while ( !Q.empty() ) { a1 = Q.top(); // printf ("==%d %d==\n",pr.first,pr.second); Q.pop(); if ( vis[a1.first] ) continue; vis[a1.first] = true; for (int i = 0 ; i < edge[a1.first].size() ; i++) // edge[a1.first].size()表示与当前点相连的点的个数 { //printf("edge[a1.first].size()= %d\n",edge[a1.first].size()); a2.first = edge[a1.first][i]; a2.second = a1.second + length[a1.first][a2.first]; if (a2.second < dis[a2.first]) { dis[a2.first] = a2.second; Q.push(a2); } } } } int main() { scanf ("%d%d",&n,&m); memset(length,-1,sizeof(length)); for (int i = 1 ; i <= m ; i++) { int x,y,z; scanf ("%d%d%d",&x,&y,&z); edge[x].push_back(y); edge[y].push_back(x); //双向存图 if (length[x][y] == -1) length[x][y] = length[y][x] = z; else length[x][y] = length[y][x] = min(z,length[x][y]); //如果出现重边，记录较小的权值。 } dijkstra(); printf ("%d\n",dis[n] == INF ? -1 : dis[n]); return 0; } /* 7 10 1 3 3 1 4 1 3 4 1 2 3 5 3 5 5 4 5 2 3 6 2 5 6 1 5 7 7 6 7 4 */
