VIJOS-P1423 最佳路线
2024-09-08 03:28:52
VIJOS-P1423 最佳路线
JDOJ 1507
https://neooj.com/oldoj/problem.php?id=1507
Description
年久失修的赛道令国际汽联十分不满。汽联命令主办方立即对赛道进行调整,否则将取消其主办权。主办方当然必须马上开始行动。 赛道测评人员经过了三天三夜的数据采集,选出了若干可以使用的道路和各道路行驶所需的时间。这些道路包括若干直道和弯道,每个直道连接两个不同的弯道且为单向,两个弯道之间可能有多条直道,通过直道和弯道都需要一定的时间。主办方打算在这些可用道路中选出一部分作为赛道。赛道是由直道和弯道交替组成的一圈,赛道可多次经过同一条弯道,因为主办方可以通过架设立交桥的方法避免撞车。为了使比赛更加精彩,主办方希望选择一条单圈时间最短的赛道,由于观众席的位置在弯道1,所以赛道必须经过弯道1(赛道至少要包含一条直道)。
Input
第一行是两个整数n,m(1< =n< =200,1< =m< =100000),分别表示弯道数和直道数。接下来n行,第i行是一个整数ai(1< =ai< =1000),表示通过第i个弯道所消耗的时间。接下来m行,第j行是三个整数xj,yj,bj(1< =xj,yj< =n,1< =bj< =1000),表示从弯道xj到弯道yj有一条单向直道,且通过该直道所消耗的时间为bj。
Output
一个整数s,表示单圈时间最短的赛道的单圈时间,若无解则输出-1。
Sample Input
【样例输入1】 3 6 1 1 2 1 2 3 2 3 5 3 1 1 3 2 1 2 1 10 1 3 15 【样例输入2】 3 4 1 1 2 1 2 4 1 3 5 2 3 5 3 2 10
Sample Output
【样例输出1】 13 【样例输出2】 -1
HINT
30%的数据满足n< =10
我们可以把弯道想象成顶点,直道想象成边。 弯道有通过时间,直道也有通过时间怎么处理呢?我们可以认为边(x,y)的权值为通过直道的时间+通过弯道y的时间和。把弯道彻底解放出来,只起到顶点的作用。
那么两个弯道有多条直道相连怎么理解和处理呢?虽然这种提法跟我们实际生活中的事物相矛盾,但是存在即合理。
解决办法很好想:题目要求的是最小的环,那么两点间的距离我们就选择那条最小的直道就行了,剔除多余的直道。 一看数据量:1< =n< =200,1< =m< =100000 ,分析题目,果断选择floyed。 并且必须经过1号弯道,其实就是求从1开始的最小的环的长度。 Ans=f[1][1];即可。
Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int ti[];
int map[][];
int main()
{
memset(map,0x3f,sizeof(map));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&ti[i]);
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(ti[y]+z<map[x][y])
map[x][y]=ti[y]+z;
}
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
if(map[][]>)
printf("-1");
else
printf("%d",map[][]);
return ;
}
最新文章
- 新编码神器Atom使用纪要
- Linux and symmetric multiprocessing
- [TYVJ]1519 博彩
- php 小试 mysql-zmq-plugin 和 pthreads
- Java集合框架源码剖析:LinkedHashSet 和 LinkedHashMap
- ThreadLocal知识总结
- ASP.NET MVC中使用事务写法
- 【转】C++的面象对象总结
- Android Fragment详解(二):Fragment创建及其生命周期
- 符号三角形(hdu 2510 搜索+打表)
- win32 调用多媒体函数PlaySound()
- 3.1 if 条件分支语句
- hg (Mercurial)multiple heads (hg 多头)、撤销 commit,并保留修改
- Python学习笔记-条件语句
- delphi XML简单处理
- luogu2178/bzoj4199 品酒大会 (SA+单调栈)
- L1-033	出生年
- js 日期格式: UTC GMT 互相转换
- SpringMVC---400错误The request sent by the client was syntactically incorrect ()
- 使用jquery刷新当前页面
热门文章
- linux下如何查看自己都装了什么服务
- Vue中MVVM模式的双向绑定原理 和 代码的实现
- 八、Spring之深入理解声明式事务
- Course: ISA 414
- Kafka随笔
- Kubernetes DaemonSet(部署守护进程)
- 使用NumPy、Numba的简单使用(二)
- C# .NET 使用 NPOI 读取 .xlsx 格式 Excel
- mysql报错com.mysql.jdbc.exceptions.jdbc4.MySQLSyntaxErrorException
- Windows 下MongoDB复制集配置