一些代码
理解
#include<bits/stdc++.h>using namespace std;//优先队列优化的链式前向星const int maxn=1000;const int INF=0x3fffffff;struct Edge{int from, to, dist;Edge(int u, int v, int d):from(u),to(v),dist(d){}};struct HeapNode{int u, d;HeapNode(int u, int d):u(u),d(d){}bool operator < (const HeapNode & r) const {return d>r.d;}};struct Dijkstra{int n, m;vector<int> G[maxn];vector<Edge> edges;int dis[maxn];int pre[maxn];int v[maxn];void AddEdge(int u, int v, int d){edges.push_back(Edge(u, v, d));G[u].push_back(edges.size()-1);}void init(int v_size){n=v_size;edges.clear();for(int i=0; i<n; i++) G[i].clear();memset(pre, 0, sizeof(pre));}void dijkstra(int s){for(int i=0; i<n; i++) dis[i]=INF;dis[s]=0;memset(v, 0, sizeof(v));priority_queue<HeapNode> Q;Q.push(HeapNode(s, 0));while(!Q.empty()){HeapNode t=Q.top();Q.pop();int x=t.u;if(v[x]) continue;v[x]=1;for(int k=0; k<G[x].size(); k++){Edge & e = edges[G[x][k]];if(dis[x]+e.dist<dis[e.to]){dis[e.to]=dis[x]+e.dist;pre[e.to]=x;Q.push(HeapNode(e.to, dis[e.to]));}}}}};int main(){int u, v, d; Dijkstra a;a.init(10);while(){cin>>u>>v>>d;a.AddEdge(u, v, d); }a.dijkstra(1);cout<<a.dis[5]<<endl;return 0;}
