链接矩阵+优先队列
#include <iostream> #include <cstring> #include <set> #include <queue> #include <limits> #include <stdio.h> using namespace std; const int maxNodes = 102; int g[maxNodes][maxNodes]; int pre[maxNodes]; int cost[maxNodes]; int maxInt = numeric_limits<int>::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<int> s; priority_queue<Node> 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<M;++i) { int row,col,val; cin>>row>>col>>val; g[row][col] = val; g[col][row] = val; } cout<<Dijkstra()<<endl; } return 0; }