最短路问题稍微复杂了一点,松弛的时候多判断一些条件就可以了。第一次用SPFA写最短路。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std; const int maxn = ;
vector<int> cost[maxn][maxn];
vector<int> ljb[maxn];
struct abc{ int start, end, aa, bb, cc; }dt[];
int flag[maxn], dist[maxn];
int n, m, sx, ex; void spfa()
{
int i, ii; flag[sx] = ;
for (i = ; i <= n; i++) dist[i] = 0x7FFFFFFF;
dist[sx] = ;
queue<int>Q; Q.push(sx);
while (!Q.empty())
{
int hh = Q.front(); Q.pop(); flag[hh] = ;
int nowtime = dist[hh];
for (ii = ; ii < ljb[hh].size(); ii++)
{
for (i = ; i < cost[hh][ljb[hh][ii]].size(); i++)
{
int id = cost[hh][ljb[hh][ii]][i];
if (dt[id].aa < dt[id].cc) continue;
int yy = nowtime % (dt[id].aa + dt[id].bb);
if (yy <= dt[id].aa)
{
if (yy + dt[id].cc <= dt[id].aa)
{
if (nowtime + dt[id].cc < dist[ljb[hh][ii]])
{
dist[ljb[hh][ii]] = nowtime + dt[id].cc;
if (!flag[ljb[hh][ii]])Q.push(ljb[hh][ii]), flag[ljb[hh][ii]] = ;
}
}
else
{
if (nowtime + dt[id].aa - yy + dt[id].bb + dt[id].cc < dist[ljb[hh][ii]])
{
dist[ljb[hh][ii]] = nowtime + dt[id].aa - yy + dt[id].bb + dt[id].cc;
if (!flag[ljb[hh][ii]])Q.push(ljb[hh][ii]), flag[ljb[hh][ii]] = ;
}
}
}
else
{
if (nowtime + dt[id].aa + dt[id].bb - yy + dt[id].cc< dist[ljb[hh][ii]])
{
dist[ljb[hh][ii]] = nowtime + dt[id].aa + dt[id].bb - yy + dt[id].cc;
if (!flag[ljb[hh][ii]])Q.push(ljb[hh][ii]), flag[ljb[hh][ii]] = ;
}
}
}
}
}
} int main()
{
int _ = ;
int i, j, u, v, a, b, c;
while (~scanf("%d%d%d%d", &n, &m, &sx, &ex))
{
for (i = ; i <= n; i++) ljb[i].clear();
for (i = ; i <= n; i++) for (j = ; j <= n; j++) cost[i][j].clear();
memset(flag, , sizeof(flag));
for (i = ; i < m; i++)
{
scanf("%d%d%d%d%d", &u, &v, &a, &b, &c);
dt[i].start = u; dt[i].end = v;
dt[i].cc = c; dt[i].aa = a; dt[i].bb = b;
cost[u][v].push_back(i);
ljb[u].push_back(v);
}
spfa();
printf("Case %d: %d\n", _++, dist[ex]);
}
return ;
}
CSU 1333 Funny Car Racing的更多相关文章
-
CSU 1333 Funny Car Racing (最短路)
题目链接: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1333 解题报告:一个图里面有n个点和m条单向边,注意是单向边,然后每条路开a秒关闭b秒 ...
-
CSU - 1333 1333: Funny Car Racing(spfa)
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1333 这题多了一个限制条件是每一条路都会规律的开放a时间关闭b时间,车子必须在开放的时候进入,在关 ...
-
Funny Car Racing CSU - 1333 (spfa)
There is a funny car racing in a city with n junctions and m directed roads. The funny part is: each ...
-
Hdu 1052 Tian Ji -- The Horse Racing
Tian Ji -- The Horse Racing Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J ...
-
csu 1812: 三角形和矩形 凸包
传送门:csu 1812: 三角形和矩形 思路:首先,求出三角形的在矩形区域的顶点,矩形在三角形区域的顶点.然后求出所有的交点.这些点构成一个凸包,求凸包面积就OK了. /************** ...
-
CSU 1503 点到圆弧的距离(2014湖南省程序设计竞赛A题)
题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1503 解题报告:分两种情况就可以了,第一种是那个点跟圆心的连线在那段扇形的圆弧范围内,这 ...
-
CSU 1120 病毒(DP)
题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1120 解题报告:dp,用一个串去更新另一个串,递推方程是: if(b[i] > a ...
-
CSU 1116 Kingdoms(枚举最小生成树)
题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1116 解题报告:一个国家有n个城市,有m条路可以修,修每条路要一定的金币,现在这个国家只 ...
-
CSU 1113 Updating a Dictionary(map容器应用)
题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1113 解题报告:输入两个字符串,第一个是原来的字典,第二个是新字典,字典中的元素的格式为 ...
随机推荐
-
【转】Duplicate Elimination in Scrapy
本文转载自:http://blog.pluskid.org/?p=381 之前介绍 Scrapy 的时候提过 Spider Trap ,实际上,就算是正常的网络拓扑,也是很复杂的相互链接,虽然我当时给 ...
-
ECshop中defined(&#39;IN_ECS&#39;)的实现原理
在PHP中经常看到如下代码 if (!defined('IN_ECS')) { die('Hacking attempt'); } 实现的原因以及原理如下: ecs ...
-
IE下判断IE版本的语句...[if lte IE 6]……[endif]
<!--[if lte IE 6]> <![endif]--> IE6及其以下版本可见 <!--[if lte IE 7]> <![endif]--> ...
-
Android名片扫描识别系统SDK
Android名片扫描识别系统SDK 一.Android名片扫描识别系统应用背景 这些年,随着移动互联的发展,APP应用成爆发式的增长,在很多APP中都涉及到对名片信息的录入,如移动CRM.移动端OA ...
-
迅速的说清楚rpc原理
第一个问题是服务提供者进程如果被kill -9暴力杀死,不能主动调用srem命令怎么办? 这个时候服务列表中多了一个黑地址指向了不存在的服务而消费者完全不知道,这个时候服务中介就成了黑中介了.那该怎么 ...
-
Laravel 返回数据库中的随机一行数据
最佳方式 $total = Book::count() - 1; $skip = mt_rand(0, $total); $item = Book::select('name', 'author_id ...
-
SpringBoot + docker + neo4j
下拉镜像 docker pull neo4j 启动镜像 docker run -d -p 7473:7473 -p 7687:7687 -p 7474:7474 neo4j 打开浏览器:http:// ...
-
h5实现手机端等级进度条
h5实现等级进度条 需求如下: 实现一个动画进度条,页面一打开实现一个进度条动画,因为App这个页面会经常改,所以没有使用原审Android或者IOS来实现,希望通过H5来做: 服务器端返回如下数据: ...
-
【网络编程】使用getnameinfo()/getaddrinfo()/InetPton()
1.简要 从前用的网络编程函数现在又做了一定的改动,报了这么3个错误. error C4996: 'inet_ntoa': Use inet_ntop() or InetNtop() instead ...
-
java(5) 线程
1.理清概念 并行与并发: *并行:多个cpu实例或者多台机器同时执行一段处理逻辑,是真正的同时. *并发:通过cpu调度算法,让用户看上去同时执行,实际上从cpu操作层面不是真正的同时.并发往往在场 ...