C++ 最短路径算法：Dijkstra 算法实现

#include #include #include #include using namespace std;

const int INF = 0x7fffffff; const int MAXN = 505;

struct Edge { int to, w; Edge(int t, int ww): to(t), w(ww) {} };

vector adj[MAXN]; int dis[MAXN]; bool vis[MAXN];

void dijkstra(int s) { fill(dis, dis + MAXN, INF); dis[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; pq.push(make_pair(0, s)); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = true; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].to, w = adj[u][i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.push(make_pair(dis[v], v)); } } } }

int main() { int n, m, s, d, w; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); adj[u].push_back(Edge(v, c)); } scanf("%d%d%d", &s, &d, &w); if(s == d) { printf("0"); return 0; } dijkstra(s); if(dis[d] == INF) printf("unreachable"); else printf("%d", dis[d]); return 0; }