![POJ - 2387 最短路 POJ - 2387 最短路](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
思路:用dijkstra算法,是无向图。
AC代码:
#include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 1000 + 5; int d[maxn]; bool vis[maxn]; struct Edge{ int from, to, dist; Edge(){} Edge(int u, int v, int d):from(u), to(v), dist(d) {} }; vector<Edge>edge; struct HeapNode{ int d, u; HeapNode() {} HeapNode(int d, int u):d(d), u(u) {} bool operator < (const HeapNode &p) const { return d > p.d; } }; vector<int>G[maxn]; void init(int n) { edge.clear(); for(int i = 0; i <= n; ++i) G[i].clear(); } void addEdge(int from, int to, int dist) { edge.push_back(Edge(from, to, dist)); int m = edge.size(); G[from].push_back(m-1); } void dijkstra(int s) { priority_queue<HeapNode>q; memset(d, inf, sizeof(d)); d[s] = 0; memset(vis, 0, sizeof(vis)); q.push(HeapNode(0, s)); while(!q.empty()) { HeapNode p = q.top(); q.pop(); int u = p.u; if(vis[u]) continue; vis[u] = 1; for(int i = 0; i < G[u].size(); ++i) { Edge &e = edge[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; q.push(HeapNode(d[e.to], e.to)); } } } } int main() { int n, m; while(scanf("%d%d", &m, &n) == 2) { init(n); int u, v, dis; for(int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &dis); addEdge(u, v, dis); addEdge(v, u, dis); } dijkstra(n); printf("%d\n", d[1]); } return 0; }
如有不当之处欢迎指出!