Subway

Description
You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want to be late for class, you want to know how long it will take you to get to school.
You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch between different subway lines if you wish. All subway lines go in both directions.
Input
Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each stop on the line, in order. You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres. Each line has at least two stops. The end of each subway line is followed by the dummy coordinate pair -1,-1. In total there are at most 200 subway stops in the city.
Output
Output is the number of minutes it will take you to get to school, rounded to the nearest minute, taking the fastest route.
Sample Input
0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1
Sample Output
21

1个回答

Subway planning
Problem Description The government in a foreign country is looking into the possibility of establishing a subway system in its capital. Because of practical reasons, they would like each subway line to start at the central station and then go in a straight line in some angle as far as necessary. You have been hired to investigate whether such an approach is feasible. Given the coordinates of important places in the city as well as the maximum distance these places can be from a subway station (possibly the central station, which is already built), your job is to calculate the minimum number of subway lines needed. You may assume that any number of subway stations can be built along a subway line. Figure 1: The figure above corresponds to the first data set in the example input. Input The first line in the input file contains an integer N, the number of data sets to follow. Each set starts with two integers, n and d (1 <= n <= 500, 0 <= d < 150). n is the number of important places in the city that must have a subway station nearby, and d is the maximum distance allowed between an important place and a subway station. Then comes n lines, each line containing two integers x and y (-100 <= x, y <= 100), the coordinates of an important place in the capital. The central station will always have coordinates 0, 0. All pairs of coordinates within a data set will be distinct (and none will be 0, 0). Output For each data set, output a single integer on a line by itself: the minimum number of subway lines needed to make sure all important places in the city is at a distance of at most d from a subway station. Sample Input 2 7 1 -1 -4 -3 1 -3 -1 2 3 2 4 2 -2 6 -2 4 0 0 4 -12 18 0 27 -34 51 Sample Output 4 2
Subway tree systems 程序的思路
Problem Description Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique central station. Imagine you are a tourist in one of these cities and you want to explore all of the subway system. You start at the central station and pick a subway line at random and jump aboard the subway car. Every time you arrive at a station, you pick one of the subway lines you have not yet travelled on. If there is none left to explore at your current station, you take the subway line back on which you first came to the station, until you eventually have travelled along all of the lines twice, once for each direction. At that point you are back at the central station. Afterwards, all you remember of the order of your exploration is whether you went further away from the central station or back towards it at any given time, i.e. you could encode your tour as a binary string, where 0 encodes taking a subway line getting you one station further away from the central station, and 1 encodes getting you one station closer to the central station. Figure 1. To the left: A subway tree system. The larger dot is the central station. To the right: Three out of several possible encodings of exploration tours for the subway system. Input On the first line of input is a single positive integer n, telling the number of test scenarios to follow. Each test scenario consists of two lines, each containing a string of the characters '0' and '1' of length at most 3000, both describing a correct exploration tour of a subway tree system. Output For each test scenario, output one line containing the text “same” if the two strings may encode exploration tours of the same subway tree system, or the text “different” if the two strings cannot be exploration tours of the same subway tree system. Sample Input 2 0010011101001011 0100011011001011 0100101100100111 0011000111010101 Sample Output same different
Subway planning
Problem Description The government in a foreign country is looking into the possibility of establishing a subway system in its capital. Because of practical reasons, they would like each subway line to start at the central station and then go in a straight line in some angle as far as necessary. You have been hired to investigate whether such an approach is feasible. Given the coordinates of important places in the city as well as the maximum distance these places can be from a subway station (possibly the central station, which is already built), your job is to calculate the minimum number of subway lines needed. You may assume that any number of subway stations can be built along a subway line. Figure 1: The figure above corresponds to the first data set in the example input. Input The first line in the input file contains an integer N, the number of data sets to follow. Each set starts with two integers, n and d (1 <= n <= 500, 0 <= d < 150). n is the number of important places in the city that must have a subway station nearby, and d is the maximum distance allowed between an important place and a subway station. Then comes n lines, each line containing two integers x and y (-100 <= x, y <= 100), the coordinates of an important place in the capital. The central station will always have coordinates 0, 0. All pairs of coordinates within a data set will be distinct (and none will be 0, 0). Output For each data set, output a single integer on a line by itself: the minimum number of subway lines needed to make sure all important places in the city is at a distance of at most d from a subway station. Sample Input 2 7 1 -1 -4 -3 1 -3 -1 2 3 2 4 2 -2 6 -2 4 0 0 4 -12 18 0 27 -34 51 Sample Output 4 2
Subway tree systems 地铁的模拟编程
Description Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique central station. Imagine you are a tourist in one of these cities and you want to explore all of the subway system. You start at the central station and pick a subway line at random and jump aboard the subway car. Every time you arrive at a station, you pick one of the subway lines you have not yet travelled on. If there is none left to explore at your current station, you take the subway line back on which you first came to the station, until you eventually have travelled along all of the lines twice,once for each direction. At that point you are back at the central station. Afterwards, all you remember of the order of your exploration is whether you went further away from the central station or back towards it at any given time, i.e. you could encode your tour as a binary string, where 0 encodes taking a subway line getting you one station further away from the central station, and 1 encodes getting you one station closer to the central station. Input On the first line of input is a single positive integer n, telling the number of test scenarios to follow.Each test scenario consists of two lines, each containing a string of the characters '0' and '1' of length at most 3000, both describing a correct exploration tour of a subway tree system. Output exploration tours of the same subway tree system, or the text "different" if the two strings cannot be exploration tours of the same subway tree system. Sample Input 2 0010011101001011 0100011011001011 0100101100100111 0011000111010101 Sample Output same different
Subway tree systems
Description Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique central station. Imagine you are a tourist in one of these cities and you want to explore all of the subway system. You start at the central station and pick a subway line at random and jump aboard the subway car. Every time you arrive at a station, you pick one of the subway lines you have not yet travelled on. If there is none left to explore at your current station, you take the subway line back on which you first came to the station, until you eventually have travelled along all of the lines twice,once for each direction. At that point you are back at the central station. Afterwards, all you remember of the order of your exploration is whether you went further away from the central station or back towards it at any given time, i.e. you could encode your tour as a binary string, where 0 encodes taking a subway line getting you one station further away from the central station, and 1 encodes getting you one station closer to the central station. ![](http://poj.org/images/1635_1.jpg) Input On the first line of input is a single positive integer n, telling the number of test scenarios to follow.Each test scenario consists of two lines, each containing a string of the characters '0' and '1' of length at most 3000, both describing a correct exploration tour of a subway tree system. Output exploration tours of the same subway tree system, or the text "different" if the two strings cannot be exploration tours of the same subway tree system. Sample Input 2 0010011101001011 0100011011001011 0100101100100111 0011000111010101 Sample Output same different

Problem Description The government in a foreign country is looking into the possibility of establishing a subway system in its capital. Because of practical reasons, they would like each subway line to start at the central station and then go in a straight line in some angle as far as necessary. You have been hired to investigate whether such an approach is feasible. Given the coordinates of important places in the city as well as the maximum distance these places can be from a subway station (possibly the central station, which is already built), your job is to calculate the minimum number of subway lines needed. You may assume that any number of subway stations can be built along a subway line. Figure 1: The figure above corresponds to the first data set in the example input. Input The first line in the input file contains an integer N, the number of data sets to follow. Each set starts with two integers, n and d (1 <= n <= 500, 0 <= d < 150). n is the number of important places in the city that must have a subway station nearby, and d is the maximum distance allowed between an important place and a subway station. Then comes n lines, each line containing two integers x and y (-100 <= x, y <= 100), the coordinates of an important place in the capital. The central station will always have coordinates 0, 0. All pairs of coordinates within a data set will be distinct (and none will be 0, 0). Output For each data set, output a single integer on a line by itself: the minimum number of subway lines needed to make sure all important places in the city is at a distance of at most d from a subway station. Sample Input 2 7 1 -1 -4 -3 1 -3 -1 2 3 2 4 2 -2 6 -2 4 0 0 4 -12 18 0 27 -34 51 Sample Output 4 2
Bus Schedules 怎么做呢
Problem Description The Association of Commuters in Montreal (ACM) wishes to create a website for the city’s publictransit commuters, in order to promote public transit. A prominent reason for people to drive to work instead of commuting is the time wasted on the subway and buses. For this reason, the ACM wishes to add a form on their website so that visitors will be able to specify two points on the island, and the website will find the quickest route between those two points using its database of subway and bus schedules. Seeing how this may help improve the environment and the greenhouse effect, you offer your help. Input The first line of each test case will contain a positive integer n, the number of bus and subway schedules which will follow. Each schedule will begin with a line containing a positive integer m, the number of stops along the path. m lines will follow, describing the stops of the day in chronological order. Each stop will begin by a time in the format hh : mm, between 00 : 00 and 23 : 59 inclusively. There will be at least one minute between each stop — in other words, all the stop times for a particular bus will be different. A single space will follow, and the rest of the line will contain a name describing the stop. The name will not contain spaces nor capital letters, and will be at most 20 characters long. Stops with the same name obviously denote the same physical location, where passengers can wait for other buses or subways to stop. After the day completes, the buses and subways mysteriously disappear and reappear at some point before their first stop. They cannot carry any passengers at that time, so the passengers must spend the night waiting at some stop.Each schedule repeats itself every day. After the schedules, a line will contain a time and two locations of at most 20 characters, the start and the goal. Output the minimum number of minutes needed for a passenger at the start location at the given time to reach the goal location. He is able to enter any bus which stops at his start location at the given starting time or later, and he can also switch from a bus to another instantaneously if they happen to stop at the same place at the same time. He can also wait at a stop for an arbitrary amount of time. Output If the destination cannot be reached, output “impossible”. The last line of the input will contain the integer 0 and should not be processed. All the numbers in the input will be at most 1000. Sample Input 2 4 00:01 loc_a 00:02 loc_b 00:10 loc_c 00:20 loc_a 2 00:02 loc_b 00:04 loc_c 00:00 loc_a loc_c 1 3 00:00 foo 01:00 bar 02:00 baz 01:30 bar foo 1 4 00:00 baz 01:00 foo 02:00 bar 03:00 baz 02:30 bar foo 0 Sample Output 4 impossible 2790

Problem Description The government in a foreign country is looking into the possibility of establishing a subway system in its capital. Because of practical reasons, they would like each subway line to start at the central station and then go in a straight line in some angle as far as necessary. You have been hired to investigate whether such an approach is feasible. Given the coordinates of important places in the city as well as the maximum distance these places can be from a subway station (possibly the central station, which is already built), your job is to calculate the minimum number of subway lines needed. You may assume that any number of subway stations can be built along a subway line. Figure 1: The figure above corresponds to the first data set in the example input. Input The first line in the input file contains an integer N, the number of data sets to follow. Each set starts with two integers, n and d (1 <= n <= 500, 0 <= d < 150). n is the number of important places in the city that must have a subway station nearby, and d is the maximum distance allowed between an important place and a subway station. Then comes n lines, each line containing two integers x and y (-100 <= x, y <= 100), the coordinates of an important place in the capital. The central station will always have coordinates 0, 0. All pairs of coordinates within a data set will be distinct (and none will be 0, 0). Output For each data set, output a single integer on a line by itself: the minimum number of subway lines needed to make sure all important places in the city is at a distance of at most d from a subway station. Sample Input 2 7 1 -1 -4 -3 1 -3 -1 2 3 2 4 2 -2 6 -2 4 0 0 4 -12 18 0 27 -34 51 Sample Output 4 2

Problem Description jiefangxuanyan and yiyi cat are universally acknowledged model couples. Once jiefangxuanyan has time, he takes a train to yiyi cat’s city and meet her. This time, as usual, jiefangxuanyan gets out from the railway station, and enters the subway, only to find that the subway stations of the whole city changes their names! As a direction idiot, jiefangxuanyan felt helpless with this situation. He called yiyi cat for help. Because the subway map is so complicated, she can’t remember it either. Fortunately, only the names of the stations changed, the structure of subway lines is the same. So she picks out the old map to make a mapping. But mapping such a confused subway map is definitely a difficult task. So she has to use the computer. Unfortunately, she just spilt wonton soup into her computer. So, yiyi cat asked you for help, hoping you can help her with this problem. The subway in the city forms a tree, with N subway stations and N-1 subway lines. Any pair of stations are connected with one or more subway lines. You need to find a bijective mapping from the old names to the new names, that for each pair of stations connected by exactly one line in the old map, their new names are also connected by exactly one line in the new map. Input The input has multiple test cases, please process to the end of file. For each test case, the first line is an integer N(1≤N≤100000). In the following N−1 lines, each line has two space-separated string, as two stations connected by one line in the old map. In the following N−1 lines, each line has two space-separated string, as two stations connected by one line in the new map. Station names are no longer than 10 characters, and only consists of lowercase letters (a~z). Output For each test case, output N lines. Each line consists two space-separated string, as the old name and its corresponding new name. Both the names appeared in the old and new subway map should appear exactly once in the output. You can output the names in any order. And if there are multiple valid mappings, output any one. Names in the old map and the new map may be the same, but this does not mean these two stations are the same. Sample Input 3 a b b c b a a c Sample Output b a a b c c
WebView加载不同的网页地址显示一样

SQL查询语句的一点困惑

echarts地图控件官方实例如何调用 显示地图

Java学习的正确打开方式

linux系列之常用运维命令整理笔录

python 简易微信实现（注册登录+数据库存储+聊天+GUI+文件传输）
socket+tkinter详解+简易微信实现 历经多天的努力，查阅了许多大佬的博客后终于实现了一个简易的微信O(∩_∩)O~~ 简易数据库的实现 使用pands+CSV实现数据库框架搭建 import socket import threading from pandas import * import pymysql import csv # 创建DataFrame对象 # 存储用户数据的表（...

Python十大装B语法
Python 是一种代表简单思想的语言，其语法相对简单，很容易上手。不过，如果就此小视 Python 语法的精妙和深邃，那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点，并附上详细的实例代码。如能在实战中融会贯通、灵活使用，必将使代码更为精炼、高效，同时也会极大提升代码B格，使之看上去更老练，读起来更优雅。

2019年11月中国大陆编程语言排行榜
2019年11月2日，我统计了某招聘网站，获得有效程序员招聘数据9万条。针对招聘信息，提取编程语言关键字，并统计如下： 编程语言比例 rank pl_ percentage 1 java 33.62% 2 cpp 16.42% 3 c_sharp 12.82% 4 javascript 12.31% 5 python 7.93% 6 go 7.25% 7 p...

《奇巧淫技》系列-python！！每天早上八点自动发送天气预报邮件到QQ邮箱

JavaScript 为什么能活到现在？

Nginx 原理和架构
Nginx 是一个免费的，开源的，高性能的 HTTP 服务器和反向代理，以及 IMAP / POP3 代理服务器。Nginx 以其高性能，稳定性，丰富的功能，简单的配置和低资源消耗而闻名。 Nginx 的整体架构 Nginx 里有一个 master 进程和多个 worker 进程。master 进程并不处理网络请求，主要负责调度工作进程：加载配置、启动工作进程及非停升级。worker 进程负责处...

Python 编程开发 实用经验和技巧
Python是一门很灵活的语言，也有很多实用的方法，有时候实现一个功能可以用多种方法实现，我这里总结了一些常用的方法和技巧，包括小数保留指定位小数、判断变量的数据类型、类方法@classmethod、制表符中文对齐、遍历字典、datetime.timedelta的使用等，会持续更新......

“狗屁不通文章生成器”登顶GitHub热榜，分分钟写出万字形式主义大作

《程序人生》系列-这个程序员只用了20行代码就拿了冠军

11月8日，由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办，科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。 　　区块链技术被认为是继蒸汽机、电力、互联网之后，下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力，电力解决了人类基本的生活需求，互联网彻底改变了信息传递的方式，区块链作为构造信任的技术有重要的价值。 　　1...
Python 植物大战僵尸代码实现(2):植物卡片选择和种植

shell脚本基础
shell简介：shell是一种脚本语言，可以使用逻辑判断、循环等语法，可以自定义函数，是系统命令的集合 文章目录shell脚本结构和执行方法shell脚本中date命令的用法 shell脚本结构和执行方法 1.shell脚本开头需要加#!/bin/bash 2.以#开头的行作为注释 3.脚本的名字以.sh结尾，用于区分这是一个shell脚本 4.执行方法有两种： 1）bash test.sh 2...
8年经验面试官详解 Java 面试秘诀

1.两种思维方式在求职面试中，经常会考察这种问题：北京有多少量特斯拉汽车？某胡同口的煎饼摊一年能卖出多少个煎饼？深圳有多少个产品经理？一辆公交车里能装下多少个乒乓球？一个正常成年人有多少根头发？这类估算问题，被称为费米问题，是以科学家费米命名的。为什么面试会问这种问题呢？这类问题能把两类人清楚地区分出来。一类是具有文科思维的人，擅长赞叹和模糊想象，它主要依靠的是人的第一反应和直觉，比如小孩...