注意:本博客代码被黑心数据Hack,有空补回来
啊啊啊这道难题总算是做出来了,首先是帅比浮云的题解发出来一下:http://www.cnblogs.com/fuyun-boy/p/5922742.html
原题目地址:https://www.luogu.org/problem/show?pid=2832
题目背景
小X来到了山区,领略山林之乐。在他乐以忘忧之时,他突然发现,开学迫在眉睫
题目描述
山区有n座山。山之间有m条羊肠小道,每条连接两座山,只能单向通过,并会耗费小X一定时间。
小X现在在1号山,他的目的是n号山,因为那里有火车站。
然而小X的体力是有限的。他每通过一条羊肠小道,就会变得更疲劳,导致他通过任意一条羊肠小道的时间都增加1。
输入输出格式
输入格式:
第一行两个数,n,m
第2行到第m+1行,每行3个数A,B,C,表示A、B之间有一条羊肠小道,可以让小X花费C的时间从A移动到B
输出格式:
两行
第一行一个数T,表示小X需要的最短时间
第二行若干个数,用空格隔开,表示小X的移动路线
例:1 4 2 5表示:小X从1号山开始,移动到4号山,再到2号山,最后到5号山。
输入输出样例
5 8
2 4 2
5 2 1
1 2 1
4 3 2
1 3 3
4 5 2
1 5 8
3 5 3
7
1 3 5
说明
n<=10000, m<=200000
数据保证没有多条最短路径
【题解】
这道题就是最短路的变体,不过从起点到终点每多走一条边就要多加一点权值。
比如说原来的权值是6+7+9+3+5,之后的权值就是6+(7+1)+(9+2)+(3+3)+(5+4)了。
下面的这个是我写的代码。我的解决方法就是加上两个数组,一个是r,一个是tr。
d数组还是spfa一如既往的d数组,是除去这道题额外的条件的数组。
tr数组是补充数组(废话),d[i]+tr[i]表示从起点走到这个点的最小花费。
r[i]是按照从起点走到第i个节点花费d[i]+tr[i]的最短路径时,最后一次的增加值。
比如说上面的那个6+(7+1)+(9+2)+(3+3)+(5+4),表示一条路径,则这条路径终点节点的r数组的值是4。
因为走到这里最后一次加上的数字是4。
pre数组不说了,帅比浮云说了很清楚。。。
#include <cstdio>
#include <cstring>
#include <queue>
#define mp make_pair
using namespace std;
int n,m,h;
struct edge
{
int v,w;
edge*next;
};
edge* link[10001];
int d[10001],r[10001],tr[10001],pre[10001];
bool v[10001];
void add(int u,int v,int w)
{
edge* p=new edge;
p->v=v;
p->w=w;
p->next=link[u];
link[u]=p;
}
void del(edge* p)
{
if(p!=NULL)
{
del(p->next);
delete p;
}
}
void spfa()
{
queue<int>q;
memset(d,0x3f,sizeof(d));
d[1]=0;
q.push(1);
v[1]=true;
while(!q.empty())
{
int x=q.front();
q.pop();
v[x]=false;
for(edge* p=link[x];p!=0;p=p->next)
{
if(d[x]+tr[x]+p->w+r[x]<d[p->v]+tr[p->v])
{
d[p->v]=d[x]+p->w;
tr[p->v]=tr[x]+r[x];
r[p->v]=r[x]+1;
pre[p->v]=x;
if(v[p->v]==false)
{
v[p->v]=true;
q.push(p->v);
}
}
}
}
}
void print(int n)
{
if(n!=1)
print(pre[n]);
printf("%d ",n);
}
int main()
{
int CO2,H2O,H2CO3;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&CO2,&H2O,&H2CO3);
add(CO2,H2O,H2CO3);
}
spfa();
printf("%d\n",d[n]+tr[n]);
print(n);
for(int i=1;i<=n;i++)
del(link[i]);
return 0;
}
祝各位NOIP2016 RP++ SCORE++
SPFA+寻路(行路难,洛谷2832)的更多相关文章
-
spfa模板(洛谷3371)
洛谷P3371 //spfa:求s到各点的最短路,可含负权边 #include <cstdio> using namespace std; ,max_m=,inf=; struct ety ...
-
【模板】负环(SPFA/Bellman-Ford)/洛谷P3385
题目链接 https://www.luogu.com.cn/problem/P3385 题目大意 给定一个 \(n\) 个点有向点权图,求是否存在从 \(1\) 点出发能到达的负环. 题目解析 \(S ...
-
洛谷P2832 行路难 分析+题解代码【玄学最短路】
洛谷P2832 行路难 分析+题解代码[玄学最短路] 题目背景: 小X来到了山区,领略山林之乐.在他乐以忘忧之时,他突然发现,开学迫在眉睫 题目描述: 山区有n座山.山之间有m条羊肠小道,每条连接两座 ...
-
NOIP2017提高组Day1T3 逛公园 洛谷P3953 Tarjan 强连通缩点 SPFA 动态规划 最短路 拓扑序
原文链接https://www.cnblogs.com/zhouzhendong/p/9258043.html 题目传送门 - 洛谷P3953 题目传送门 - Vijos P2030 题意 给定一个有 ...
-
洛谷P1342 请柬(SPFA)
To 洛谷.1342 请柬 题目描述 在电视时代,没有多少人观看戏剧表演.Malidinesia古董喜剧演员意识到这一事实,他们想宣传剧院,尤其是古色古香的喜剧片.他们已经打印请帖和所有必要的信息和计 ...
-
洛谷P1144 最短路计数(SPFA)
To 洛谷.1144 最短路计数 题目描述 给出一个N个顶点M条边的无向无权图,顶点编号为1-N.问从顶点1开始,到其他每个点的最短路有几条. 输入输出格式 输入格式: 输入第一行包含2个正整数N,M ...
-
洛谷.4015.运输问题(SPFA费用流)
题目链接 嗯..水题 洛谷这网络流二十四题的难度评价真神奇.. #include <queue> #include <cstdio> #include <cctype&g ...
-
【题解】洛谷P1073 [NOIP2009TG] 最优贸易(SPFA+分层图)
次元传送门:洛谷P1073 思路 一开始看题目嗅出了强连通分量的气息 但是嫌长没打 听机房做过的dalao说可以用分层图 从来没用过 就参考题解了解一下 因为每个城市可以走好几次 所以说我们可以在图上 ...
-
洛谷P1186 玛丽卡 spfa+删边
洛谷P1186 玛丽卡http://blog.csdn.net/huihao123456/article/details/73414139题目描述 麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复. ...
随机推荐
-
OC初步 (一)
OC完全兼容C, 代码后缀名一般习惯用 *.m 或 *.mm,按惯例从 "Hello,World!" 开始,我们编写一个 test.mm 文件如下: #import <Fou ...
-
CSS书写规范、命名规范、网易CSS框架NEC
网易CSS框架NEC:http://nec.netease.com/ NEC框架的CSS规范: CSS规范 - 分类方法 CSS规范 - 命名规则 CSS规范 - 代码格式 CSS规范 - 优化方案 ...
-
java中Jbutton常用设置
. 对JButton大小的设置 ——因为JButen是属于小器件类型的,所以一般的setSize不能对其惊醒大小的设置,所以一般我们用 button.setPreferredSize( ...
-
css3动画在动作结束时保持该状态不变的解决办法
animation-fill-mode : none | forwards | backwards | both; none:不改变默认行为. forwards :当动画完成后,保持最后一个属性值(在 ...
-
[moka同学摘录]Yii2 csv数据导出扩展
yii2-thecsv(Yii2框架csv数据导出扩展) github: https://github.com/13552277443/yii2-thecsv 1.安装 运行 php composer ...
-
【jdbcTemplate】使用jdbcTemplate查询的三种回调
用于查询的回调接口定义主要有以下三种: org.springframework.jdbc.core.ResultSetExtractor. 基本上属于JdbcTemplate内部使用的Callbac ...
-
JavaScript笔记之第五天
JavaScript 对象 JavaScript 中的所有事物都是对象:字符串.数值.数组.函数... 此外,JavaScript 允许自定义对象. 所有事物都是对象 JavaScript 提供多个内 ...
-
cocos2dx 屏幕分辨率
http://cn.cocos2d-x.org/article/index?type=cocos2d-x&url=/doc/cocos-docs-master/manual/framework ...
-
android基础---->;发送和接收短信
收发短信应该是每个手机最基本的功能之一了,即使是许多年前的老手机也都会具备这项功能,而Android 作为出色的智能手机操作系统,自然也少不了在这方面的支持.今天我们开始自己创建一个简单的发送和接收短 ...
-
[TEST123] Performance Test
https://blog.csdn.net/zhouping19851013/article/details/82870789 https://www.cnblogs.com/jackei/archi ...