Dijkstra（单源最短路径问题）
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const int maxn = 1000;const int INF = 0x7fffffff;struct HeapNode { int d, u; bool operator < (const HeapNode& rhs) const { return d > rhs.d; }};struct Edge{ int from, to, dist;};struct Dijkstra { int n, m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; int d[maxn]; int p[maxn]; void init(int n) { this->n = n; for(int i = 0; i < n; i++) { G[i].clear(); } edges.clear(); } void AddEdge(int from, int to, int dist) { edges.push_back( (Edge) {from, to, dist} ); m = edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { priority_queue<HeapNode> Q; for(int i = 0; i < n; i++) d[i] = INF; d[s] = 0; memset(done, 0, sizeof(done)); Q.push((HeapNode){0, s}); while(!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if(done[u]) continue; done[u] = true; for(int i = 0; i < (int)G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; Q.push((HeapNode){d[e.to], e.to}); } } } }};Dijkstra t;int main(){ int n, m; int start; int from, to, dist; scanf("%d%d", &n, &m); t.init(n); for(int i = 0; i < m; i++) { scanf("%d%d%d", &from, &to, &dist); t.AddEdge(from, to, dist); } cin >> start; t.dijkstra(start); for(int i = 0; i < n; i++) { cout << t.d[i] << ' '; } cout << endl; return 0;}/***********************data:6 90 2 50 3 301 0 21 4 82 1 152 5 74 3 45 4 185 3 100***********************/