poj 3159(差分约束经典题)
2024-10-21 15:28:08
题目链接:http://poj.org/problem?id=3159思路:题目意思很简单,都与给定的条件dist[b]-dist[a]<=c,求dist[n]-dist[1]的最大值,显然这是差分约束的经典题,条件可以转化为dist[b]<=dist[a]+c,于是a->b直接连边,边权值为c,从而题目转化为图上求1->n的最短路,看了一下数据,30000个点,150000条边,果断用Dijkstra+priority_queue,1300MS+险过,orz.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAXN 30030
#define inf 1<<30
typedef pair<int,int>Pair; struct Edge{
int v,w;
Edge(int vv,int ww):v(vv),w(ww){}
}; int dist[MAXN];
bool mark[MAXN];
int n,m; vector<vector<Edge> >map; int Dijkstra(int u)
{
memset(mark,false,(n+)*sizeof(bool));
for(int i=;i<=n;i++)dist[i]=inf;
dist[u]=;
priority_queue<Pair,vector<Pair>,greater<Pair> >Q;
Q.push(make_pair(,u));
while(!Q.empty()){
Pair pp=Q.top();
Q.pop();
int dd=pp.first,u=pp.second;
if(mark[u])continue;
mark[u]=true;
for(int i=;i<map[u].size();i++){
int v=map[u][i].v,w=map[u][i].w;
if(mark[v])continue;
if(dd+w<dist[v]){
dist[v]=dd+w;
Q.push(make_pair(dist[v],v));
}
}
}
return dist[n];
} int main()
{
int u,v,w;
scanf("%d%d",&n,&m);
map.clear();map.resize(n+);
while(m--){
scanf("%d%d%d",&u,&v,&w);
map[u].push_back(Edge(v,w));
}
printf("%d\n",Dijkstra());
return ;
}
最新文章
- SQL 常用脚本
- 【 D3.js 入门系列 --- 5 】 如何添加坐标轴
- css+div绝对定位
- 来自平时工作中的javascript知识的积累---持续补充中
- Spring的5种通知
- Java-note-字符串连接
- [改善Java代码]使用构造函数协助描述枚举项
- JDBC——Sql Server
- Intel 英特尔
- cocos2d-x -------之笔记篇 环境的安装
- C#操作 Advantage Database Server 数据库
- Python 2.7.3的文件编码问题,print在控制台下面中文乱码问题,以及推荐做法
- X11 基本绘图
- 代码重构:用工厂+策略模式优化冗余的if else代码块
- Selenium中三种等待的使用方式---规避网络延迟、代码不稳定问题
- 图解HTTP系列
- 为 Html 5 和 CSS 3.0 而生——Modernizr的介绍和使用
- IE中window的模态框与返回值
- windows 环境使用 kafka
- jmeter 逻辑控制器Logic Controller详解
热门文章
- 【js类库Rapha&#235;l】基于svg中的path画40%表示的环型图
- System.IO之内存映射文件共享内存
- django-pagination的使用
- 用Swift重写公司OC项目(Day2)--创建OC与Swift的桥接文件,进而调用OC类库
- [读行者][学习LinqExpression和Reflection(Emit)]阅读TypeBuilderSample之ExampleFromTheArticle
- R语言实战读书笔记2—创建数据集(上)
- android不要标题栏
- “我爱淘”冲刺阶段Scrum站立会议2
- php7+apache的环境安装配置
- asp.net页面的请求处理响应的过程描述