本文共 1651 字，大约阅读时间需要 5 分钟。
这题 注意点 ：
用vector模拟 邻接表每个Case需要 清空vector （切记）
可以只用一个Edge对象 同时表示 优先队列的（顶点，距离）对象 又表示边集合
优先队列 比较的两种写法 一种写成friend形式（不能加const） 一种末尾必须加const
0ms AC
#include#include #include #define MAXN 105#define INF 9999999#define MAXM 10005using namespace std;struct Edge{ int to, w; Edge(){} Edge(int t, int we){ to = t; w = we; } bool operator < (const Edge &o) const{ return w > o.w; } };//struct Node{//可以用 Edge取代 这个// int u, d;// Node(){}// Node(int u1, int d1):u(u1),d(d1){}//这是 初始化列表的方法// friend bool operator < (const Node &a, const Node &b){// return a.d > b.d;// } //};int n, m;bool vis[MAXN];int dis[MAXN];vector adj[MAXN];int dijkstra(){ priority_queue pq; memset(vis,false, sizeof(vis)); memset(dis,INF,sizeof(dis)); dis[1] = 0; pq.push(Edge(1,0)); while(!pq.empty()){ Edge t = pq.top(); int cur = t.to; if(cur == n){ return dis[n]; } vis[cur] = true;//每次只有这里（距离确定的时候设置为已经访问） pq.pop(); for(int i = 0; i < adj[cur].size(); ++i){ Edge e = adj[cur][i];//貌似 不能直接用 adj[i][j]当Edge用 if(!vis[e.to]){ if(dis[e.to] > dis[cur] + e.w){ dis[e.to] = dis[cur] + e.w; pq.push(Edge(e.to, dis[e.to]));// （顶点，距离） } } } }}int main() { int i, j, a, b, c; while(scanf("%d%d",&n,&m) && n!=0 && m!=0){ for(i = 1; i <= n; ++i) adj[i].clear(); //一定 记得清除 数据 for(i = 1; i <= m; ++i){ scanf("%d%d%d",&a,&b,&c); adj[a].push_back(Edge(b,c)); adj[b].push_back(Edge(a,c)); } int ans = dijkstra(); printf("%d\n",ans);// for(i = 1; i <= n; ++i){// for(j = 0; j < adj[i].size(); ++j){// Edge e = adj[i][j];// printf("%d %d %d\n",i,e.to,e.w);// } // } } }
转载地址：http://amimi.baihongyu.com/