关于链式前向星。

 

一些代码

理解

#include
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 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)    G[i].clear();memset(pre, 0, sizeof(pre));}void dijkstra(int s){for(int i=0; iINF;dis[s]=0;memset(v, 0, sizeof(v));priority_queue 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){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<5]<<endl;return 0;
}