POJ - 2387 最短路
2024-09-12 11:16:13
思路:用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; }
如有不当之处欢迎指出!
最新文章
- 【Pyrosim案例】01:空气流动
- typeScence
- Android Content Provider Guides
- PostgreSql常用脚本
- Hanoi问题
- Mysql BLOB和TEXT类型
- Vrapper-Eclipse的vim插件安装方法
- CSS3绘制旋转的太极图案(一)
- Apache Spark源码走读之2 -- Job的提交与运行
- CentOS 7 网络配置方法
- CodeForces 55D Beautiful numbers(数位dp)
- 近 100 个 Linux 常用命令大全
- Comparable与compareTo
- css渐变/背景
- FUDCon - FedoraProject
- JavScript--表单提交
- 输入法无法切换 win10
- elementUI表格排序问题
- 转发 .Net平台下ActiveMQ入门实例 https://www.cnblogs.com/madyina/p/4121458.html
- Address localhost:1099 is already in use