玛丽卡(codevs 1021)
2024-09-07 01:43:46
题目描述 Description
麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复。
因为她和他们不住在同一个城市,因此她开始准备她的长途旅行。
在这个国家中每两个城市之间最多只有一条路相通,并且我们知道从一个城市到另一个城市路上所需花费的时间。
麦克在车中无意中听到有一条路正在维修,并且那儿正堵车,但没听清楚到底是哪一条路。无论哪一条路正在维修,从玛丽卡所在的城市都能到达麦克所在的城市。
玛丽卡将只从不堵车的路上通过,并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间,这样他就能保证他的女朋友离开该城市足够远。
编写程序,帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。
输入描述 Input Description
第一行有两个用空格隔开的数N和M,分别表示城市的数量以及城市间道路的数量。1≤N≤1000,1≤M≤N*(N-1)/2。城市用数字1至N标识,麦克在城市1中,玛丽卡在城市N中。
接下来的M行中每行包含三个用空格隔开的数A,B和V。其中1≤A,B≤N,1≤V≤1000。这些数字表示在A和城市B中间有一条双行道,并且在V分钟内是就能通过。
输出描述 Output Description
输出文件的第一行中写出用分钟表示的最长时间,在这段时间中,无论哪条路在堵车,玛丽卡应该能够到达麦克处,如果少于这个时间的话,则必定存在一条路,该条路一旦堵车,玛丽卡就不能够赶到麦克处。
样例输入 Sample Input
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
样例输出 Sample Output
27
/*
先spfa一遍,把最短路径记下来,然后枚举路径上的边,标志位不能走,
再spfa,取最短路的最大值
*/
#include<cstdio>
#include<iostream>
#define M 110
using namespace std;
int a[M][M],map[M][M],fa[M][M],q[M],n;
int main()
{
freopen("jh.in","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
scanf("%d",&map[i][j]),
a[i][j]=map[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
if(map[i-][j-]>map[i-][j])
{
map[i][j]+=map[i-][j-];
fa[i][j]=j-;
}
else
{
map[i][j]+=map[i-][j];
fa[i][j]=j;
}
int ans=,p1=,p2=n;
for(int i=;i<=n;i++)
if(map[n][i]>ans)
{
ans=map[n][i];
p1=i;
}
printf("%d\n",ans);
while(fa[p2][p1])
{
q[p2]=a[p2][p1];
p1=fa[p2][p1];
p2--;
}
printf("%d",a[][]);
for(int i=;i<=n;i++)
printf("-%d",q[i]);
return ;
}
最新文章
- angular使用post、get向后台传参的问题
- 【原】十张javascript思维导图
- 【原/转】iOS中非常强大的过滤器:NSPredicate
- 一步一步配置NLB
- RewriteRule参数
- 树状数组HDU1166
- 解决WCF大数据量传输 ,System.Net.Sockets.SocketException: 远程主机强迫关闭了一个现有的连接
- linux内核书籍
- 从Spark-Shell到SparkContext的函数调用路径过程分析(源码)
- XMAL 中x名称控件的Auttribute
- re模块 | Python 3.5
- 关于tarjan算法的空间优化
- 修改织梦默认栏目页、文章页URL命名规则,简化目录结构
- Dapper.Contrib拓展及数据库生成实体
- 20 ViewPager Demo4自动轮播
- Fibonacci数列的解法
- python中的矩阵、多维数组
- Python enumerate() 函数
- Sql Server 中将由逗号“,”分割的一个字符串转换为一个表集,并应用到 in 条件中
- Linux之vi/vim编辑器