POJ - 1797 Heavy Transportation 单源最短路
2024-08-28 01:44:59
思路:d(i)表示到达节点i的最大能运输的重量,转移方程d(i) = min(d(u), limit(u, i));注意优先队列应该以重量降序排序来重载小于符号。
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, 0, sizeof(d)); d[s] = inf; memset(vis, 0, sizeof(vis)); q.push(HeapNode(inf, 1)); while(!q.empty()) { HeapNode p = q.top(); q.pop(); int u = p.u; if(vis[u]) continue; for(int i = 0; i < G[u].size(); ++i) { Edge &e = edge[G[u][i]]; int w = min(d[u], e.dist); if(d[e.to] < w) { d[e.to] = w; q.push(HeapNode(d[e.to], e.to)); } } } } int main() { int T, n, m; scanf("%d", &T); int kase = 1; while(T--) { scanf("%d%d", &n, &m); 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(1); printf("Scenario #%d:\n", kase++); printf("%d\n\n", d[n]); } return 0; }
如有不当之处欢迎指出!
最新文章
- C#高级二
- PHP与MySQL的交互(mysqli)
- 理解Ruby中的作用域
- Debug与Release的区别
- 第七课第一节,T语言流程语句( 版本5.0)
- devexpress表格控件gridcontrol设置隔行变色、焦点行颜色、设置(改变)显示值、固定列不移动(附源码)
- 【转】内网yum源搭建
- WinAPI: FindWindow、FindWindowEx - 查找窗口
- Computer Science Theory for the Information Age-3: 高维空间中的高斯分布和随机投影
- Redis中的value包含中文显示的问题?
- Push Notification总结系列(一)
- sed进阶N;P;D
- c#一些特殊语法
- AngularJS学习之旅—AngularJS 指令(三)
- RabbmitMQ-组成及简单使用
- CPU型号各个字母的含义
- AttributeError: module ‘tensorflow.python.ops.nn’ has no attribute ‘leaky_relu’
- 【刷题】UOJ #274 【清华集训2016】温暖会指引我们前行
- java版云笔记(七)之事务管理
- visual stuidio2010 在iis中调试。
热门文章
- Linux指令--wc
- android webview加载网络连接
- 了解ViewFlipper工作机制
- php 通过curl获取远程数据,返回的是一个数组型的字符串,高手帮忙如何将这个数组类型的字符串变成数组。
- 将centos_yum源更换为阿里云(官方文档)
- 32位系统装4G以上的内存
- [DeeplearningAI笔记]Multi-class classification多类别分类Softmax regression_02_3.8-3.9
- IOS 时间字符串转换时间戳失败问题
- Git:warning: LF will be replaced by CRLF
- jquery 中json数组的操作 增删改