本文共 1263 字，大约阅读时间需要 4 分钟。
链接矩阵+优先队列
#include #include #include #include #include #include using namespace std;const int maxNodes = 102;int g[maxNodes][maxNodes];int pre[maxNodes];int cost[maxNodes];int maxInt = numeric_limits ::max();int N = 101;int M = 10001;class Node{ public: int m_id; int m_distance; Node(int id,int disc):m_id(id),m_distance(disc){} friend bool operator < (const Node &a,const Node &b)//从小到大排序 { return a.m_distance >b.m_distance; }};int Dijkstra()//起始点是1,结束点是N,返回1-->N的最小值;点与点之间没有连接设为0，这个设置不合适，应该设为正无穷{ memset(pre,-1,sizeof(pre)); cost[1] = 0; for(int i=2;i<=N;++i) cost[i] = maxInt; set s; priority_queue q; q.push(Node(1,0));//只要压入起始点即可 while (!q.empty()) { Node node = q.top(); q.pop(); if(s.find(node.m_id)!=s.end())//因为可能会把一个点多次压入队列中，但是弹出到S中的就是最小距离的，以后再弹出这个点就不再处理 continue; s.insert(node.m_id); int curr = node.m_id; for (int i=1;i<=N;++i) { if (g[curr][i]>0 && s.find(i)==s.end()) { if(cost[i] >(cost[curr] + g[curr][i])) { cost[i] = cost[curr] + g[curr][i]; q.push(Node(i,cost[i]));//i结点可能是重复插入到队列中 } } } } return cost[N];}int main(){ while (scanf("%d%d",&N,&M)!=EOF) { if(N==0 && M==0) break; memset(g,0,sizeof(g)); for (int i=0;i >row>>col>>val; g[row][col] = val; g[col][row] = val; } cout< <
转载地址：http://mbeti.baihongyu.com/