由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 面试题求解 (转载)
相关主题
面试题 -算法?一道面试题
一道C++面试题讨论几个面试题
[合集] 微软的一个面试题一道bit operator面试题
求问一道动态规划的题目Interview question for Quant to share-3, please discuss and help each other
笨笨的问一个JAVA小问题看一道面试题
贡献一下:本版上搜集的 Google 面试题 (转载)这个面试题很confusing 大家帮忙解释一下
find the subarray问一道面试题
又一道面试题,我是不是想多了?an interview question
相关话题的讨论汇总
话题: road话题: integers话题: output话题: day话题: her
进入Programming版参与讨论
1 (共1页)
Y*S
发帖数: 74
1
【 以下文字转载自 JobHunting 讨论区 】
发信人: YES (NO,NO,NO), 信区: JobHunting
标 题: 面试题求解
发信站: BBS 未名空间站 (Sat Nov 26 01:00:25 2016, 美东)
毕业很多年了。 现在有个面试题要求完成,读完后完全没有头绪,帮忙看看该怎么做
?万分感谢。
Ms.Kox enjoys her job, but she does not like to waste extra time traveling
to and from her office. After working for many years, she knows the shortest
-distance route to her office on a regular day.
Recently, the city began regular maintenance of various roads. Every day a
road gets blocked and no one can use it that day, but all other roads can be
used. You are Ms. Kox's new intern and she needs some help. Every day, you
need to determine the minimum distance that she has to travel to reach her
office.
Input Format
There are N cities numbered 0 to N-1 and M bidirectional roads.
The first line of the input contains two integers N and M.
M lines follow, each containing three space-separated integers u , v and
w, where u and v are cities connected by a bi-directional road and w is the
length of this road. There is at most one road between any two cities and
no road connects a city to itself.
The next line contains two integers S and D. S is the city where Ms. Kox
lives and D is the city where her office is located.
The next line contains an integer Q, the number of queries.
Q lines follow, each containing two integers u and v, where the road
between u and v has been blocked that day.
Constraints
0 < N < 200,000
0 < M < 200,000
0 < Q < 200,000
0 < w < 1001
0 <= S,D <= N
Output Format
Output Q lines, with each line containing the minimum distance Ms.Kox has to
travel on that day. If there is no path, print "Infinity".
Sample Input
6 9
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
2 4 5
3 5 8
1 3 3
0 2 4
0 5
9
0 1
1 2
2 3
3 4
4 5
2 4
3 5
1 3
0 2
Sample Output
7
6
6
8
11
5
5
5
5
z*********e
发帖数: 10149
2
dp?

shortest
be

【在 Y*S 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: YES (NO,NO,NO), 信区: JobHunting
: 标 题: 面试题求解
: 发信站: BBS 未名空间站 (Sat Nov 26 01:00:25 2016, 美东)
: 毕业很多年了。 现在有个面试题要求完成,读完后完全没有头绪,帮忙看看该怎么做
: ?万分感谢。
: Ms.Kox enjoys her job, but she does not like to waste extra time traveling
: to and from her office. After working for many years, she knows the shortest
: -distance route to her office on a regular day.
: Recently, the city began regular maintenance of various roads. Every day a

g***i
发帖数: 4272
3
这个就是个教科书课后题的dijkstra算法的实现吧
翻翻大学课本
1 (共1页)
进入Programming版参与讨论
相关主题
an interview question笨笨的问一个JAVA小问题
MatLab Code贡献一下:本版上搜集的 Google 面试题 (转载)
C -> assemblyfind the subarray
DNode又一道面试题,我是不是想多了?
面试题 -算法?一道面试题
一道C++面试题讨论几个面试题
[合集] 微软的一个面试题一道bit operator面试题
求问一道动态规划的题目Interview question for Quant to share-3, please discuss and help each other
相关话题的讨论汇总
话题: road话题: integers话题: output话题: day话题: her