【POJ3268】【Silver Cow Party】【反向dij】【sizeof失效】

2024-08-31 16:48

本文主要是介绍【POJ3268】【Silver Cow Party】【反向dij】【sizeof失效】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Silver Cow Party
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 15522 Accepted: 7039

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively:  NM, and  X 
Lines 2.. M+1: Line  i+1 describes road  i with three space-separated integers:  AiBi, and  Ti. The described road runs from farm  Ai to farm  Bi, requiring  Ti time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output

10

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

Source

USACO 2007 February Silver

sizeof() 失效


#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;int N,M,X;
int g[1010][1010];
int d1[1010];
int d2[1010];
bool vis[1010];
const int INF = 0x7fffffff/100;
void dij(int g[1010][1010],int d[1010])
{rep(i,0,N) d[i] = INF;memset(vis,0,sizeof(vis));d[X] = 0;rep(i,0,N-1){int dmin = INF;int p = -1;rep(j,0,N) {if(!vis[j] &&  d[j] < dmin){dmin = d[j];p = j;}}vis[p] = true;rep(j,0,N) {if(!vis[j] && d[j] > d[p] + g[p][j]){d[j] = d[p] + g[p][j];}}}
}void travs()
{rep(i,0,N) rep(j,i,N) {int tmp = g[i][j];g[i][j] = g[j][i];g[j][i] = tmp;}
}
int main()
{while(scanf("%d%d%d",&N,&M,&X) != EOF){X --;rep(i,0,N) rep(j,0,N) g[i][j] = INF;rep(i,0,M) {int u,v,w;scanf("%d%d%d",&u,&v,&w);u--,v--;g[u][v] = min(g[u][v],w);}dij(g,d1);travs();dij(g,d2);int maxs = -1;for(int i=0;i<N;i++){if(maxs < d1[i] + d2[i]){maxs = d1[i] + d2[i];}}printf("%d\n",maxs);}return 0;
}


这篇关于【POJ3268】【Silver Cow Party】【反向dij】【sizeof失效】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1124448

相关文章

浅析CSS 中z - index属性的作用及在什么情况下会失效

《浅析CSS中z-index属性的作用及在什么情况下会失效》z-index属性用于控制元素的堆叠顺序,值越大,元素越显示在上层,它需要元素具有定位属性(如relative、absolute、fi... 目录1. z-index 属性的作用2. z-index 失效的情况2.1 元素没有定位属性2.2 元素处

MySQL进阶之路索引失效的11种情况详析

《MySQL进阶之路索引失效的11种情况详析》:本文主要介绍MySQL查询优化中的11种常见情况,包括索引的使用和优化策略,通过这些策略,开发者可以显著提升查询性能,需要的朋友可以参考下... 目录前言图示1. 使用不等式操作符(!=, <, >)2. 使用 OR 连接多个条件3. 对索引字段进行计算操作4

Goland debug失效详细解决步骤(合集)

《Golanddebug失效详细解决步骤(合集)》今天用Goland开发时,打断点,以debug方式运行,发现程序并没有断住,程序跳过了断点,直接运行结束,网上搜寻了大量文章,最后得以解决,特此在这... 目录Bug:Goland debug失效详细解决步骤【合集】情况一:Go或Goland架构不对情况二:

mysql外键创建不成功/失效如何处理

《mysql外键创建不成功/失效如何处理》文章介绍了在MySQL5.5.40版本中,创建带有外键约束的`stu`和`grade`表时遇到的问题,发现`grade`表的`id`字段没有随着`studen... 当前mysql版本:SELECT VERSION();结果为:5.5.40。在复习mysql外键约

Spring常见错误之Web嵌套对象校验失效解决办法

《Spring常见错误之Web嵌套对象校验失效解决办法》:本文主要介绍Spring常见错误之Web嵌套对象校验失效解决的相关资料,通过在Phone对象上添加@Valid注解,问题得以解决,需要的朋... 目录问题复现案例解析问题修正总结  问题复现当开发一个学籍管理系统时,我们会提供了一个 API 接口去

oracle数据库索引失效的问题及解决

《oracle数据库索引失效的问题及解决》本文总结了在Oracle数据库中索引失效的一些常见场景,包括使用isnull、isnotnull、!=、、、函数处理、like前置%查询以及范围索引和等值索引... 目录oracle数据库索引失效问题场景环境索引失效情况及验证结论一结论二结论三结论四结论五总结ora

SpringBoot嵌套事务详解及失效解决方案

《SpringBoot嵌套事务详解及失效解决方案》在复杂的业务场景中,嵌套事务可以帮助我们更加精细地控制数据的一致性,然而,在SpringBoot中,如果嵌套事务的配置不当,可能会导致事务不生效的问题... 目录什么是嵌套事务?嵌套事务失效的原因核心问题:嵌套事务的解决方案方案一:将嵌套事务方法提取到独立类

MySQL的索引失效的原因实例及解决方案

《MySQL的索引失效的原因实例及解决方案》这篇文章主要讨论了MySQL索引失效的常见原因及其解决方案,它涵盖了数据类型不匹配、隐式转换、函数或表达式、范围查询、LIKE查询、OR条件、全表扫描、索引... 目录1. 数据类型不匹配2. 隐式转换3. 函数或表达式4. 范围查询之后的列5. like 查询6

Linux如何做ssh反向代理

SSH反向代理是一种通过SSH协议实现的安全远程访问方式,它允许客户端通过SSH连接到一台具有公网IP的代理服务器,然后这台代理服务器再将请求转发给内部网络中的目标主机。以下是实现SSH反向代理的步骤: 一、准备工作 确保服务器配置: 内网服务器(目标主机)和外网服务器(代理服务器)都安装了SSH服务,并且能够通过SSH进行互相访问。内网服务器上的服务(如Web服务、数据库服务等)需要在本地

Nginx反向代理功能及动静分离实现

一:Nginx支持正向代理和反向代理 1.正向代理 正向代理,指的是通过代理服务器 代理浏览器/客户端去重定向请求访问到目标服务器 的一种代理服务。 正向代理服务的特点是代理服务器 代理的对象是浏览器/客户端,也就是对于目标服务器 来说浏览器/客户端是隐藏的。 正向代理是客户端指定让代理去访问哪个服务,代表客户端的利益。 2.反向代理 反向代理,指的是浏览器/客户端并不知道自己要