Y*********d
发帖数: 47 | 1 R个银行，index从0开始到R-1，K个司机，R >= K+1。司机全部从第0个银行开始同时出
发，目的地为index 1到K的银行。任意一个司机可以把index 1到K中任意一个银行作为
他的目的地。但是一个银行只能接纳一个司机，如果多个司机同时开到同一个index为1
至K中的一个银行，那么其中一个司机下车，其余司机继续开去其他目的地银行 。银行
i 与银行 j 之间的路程长度用一个字符表示，'-'代表i和j不通，通的话这个字符会
是'1'至'9'之间的一个。每段路程是双向的，允许多个司机同时开。所有的司机都会选
最短的路程到达index 1到K的银行。如果任何一段路程在任意时间内只有一个司机在上
面开，那么那个司机就被认为是不安全行驶。在满足以上条件下，写程序算出最少能有
几个司机不安全行驶。
Constraints
1 <= K <= 49
- K+1 <= R <= 50
- Connections will contain R elements, where R is defined as K+1 <= R <= 50
- Each element of connections will contain R characters
- Value of each character in each element of connections will either '-', if
no connection is present, or one of: ['1','9']
- For each x, connections[x][x] will be '-'
- For each pair (x,y), connections[x][y] will be equal to connections[y][x]
- For each 1 <= x <= K, destination branch x will be always be reachable
from branch 0 using one or more connections
Input Format
Line 1: K
Line 2: Comma separated lists, specifying connections
Sample Input
3
-234,2---,3---,4---
Output
3
总共4个银行，3个司机。 只有从银行0到其他银行的3段路程。 在最快到达的前提下，
3个司机都只能不安全行驶。 |
Y*********d
发帖数: 47 | 2 我试了一下用Dijkstra把从银行0到其他每个银行的最短路线算出来，然后把银行1到银
行K的所有最短路线上的非末端节点银行从1到K里面剔除，剩下的应该是只有一个司机
去过的银行，凡是最后到达这些银行的司机，肯定在某段路上单独行驶过，那么这些银
行数量就等于不安全行驶的司机数量。但是运行一些test case出来的结果总是比题目
的expected output要来的大，有没有牛人来指点一下应该怎么做？小弟在这多谢了啊
！ |
T******e
发帖数: 157 | 3 可否这样，首先找出所有跟0联通的点，再对每一个点做DFS算出以这个点为出口大概可
以有走多少银行，如果银行数量够司机的话就结束，不够的话再从下一个跟0连通的没
有访问的出口开始，最后跟0独立连通的出口个数就是结果 |
Y*********d
发帖数: 47 | 4 好像不对吧，司机都要走最短路线，而且司机的所有目的地必须是1到K的银行。这样的
走法每个司机不一定是最短路线而且不一定到指定的目的地，还是需要用Dijkstra算法
算出从银行0分别到 银行1，银行2，...银行K的最短路线吧，然后从这些最短路线里看
哪条路段只有一个司机走过？
【在 T******e 的大作中提到】
: 可否这样，首先找出所有跟0联通的点，再对每一个点做DFS算出以这个点为出口大概可
: 以有走多少银行，如果银行数量够司机的话就结束，不够的话再从下一个跟0连通的没
: 有访问的出口开始，最后跟0独立连通的出口个数就是结果
|
T******e
发帖数: 157 | 5 我之前以为是要求单独开车的司机最少，如果需要满足路线最短，那么其实对每一个
input，单独开车的司机数是固定的？
有个问题，算出0到k的最短路径后，如何知道这个节点是不是末端？是把经过的最短路
线存起来，然后重新构建一个树结构吗？ |
Y*********d
发帖数: 47 | 6 要在所有司机都开最短路线的前提下，使得单独开车的司机数量最少，对应于每个
input, 这个数量应该是固定的。
Dijkstra的算法除了算出0节点到i节点的最短路线距离外，还会记录在这个最短路线上
i节点的前一个节点是什么。我的理解是，既然有K个司机最终分别到达1节点至K节点，
那么从1节点到K节点中，剔除那些作为前节点出现过的，剩下的应该是只有1个司机访
问过的节点，也就是那个司机单独开过到达此类节点的路段，所以剩下的节点数量应该
是单独开车的司机数量。但是我的结果在大多数test case上运行都比标准答案大，不
明白这个算法错在哪里。
原题：
There are R bank locations and there are K drivers to transfer deposits to
those locations. R >= K+1 and all bank locations are numbered from 0 to R-1.
Location 0 is the branch where all drivers start at time 0 and take the
deposits to other branches. For each i between 1 and K, inclusive, location
i is the destination branch for any one of the drivers. A bank is expecting
at most one driver.
Drivers can travel from one bank to another. Some bank branches are
bidirectionally connected and others are not connected. The connections
between branches are given as comma separated lists of characters called "
connections". If there is no connection between branch i and j, then the ith
String of the list at index j will be '-', otherwise it will contain a
single digit '1'-'9', representing the number of hours it takes for a driver
to drive from bank i to bank j.
All drivers can move at the same time in their individual vans, and multiple
drivers can move along the same connection. If a group of drivers reaches a
branch that is the destination branch for one of them, that driver stops
his van and enters the branch and the remaining drivers continue to other
branch locations.
Safety of drivers is defined as follows:
- A driver is safe at any given time if his or her van is accompanied by at
least one other driver's van
- If driver is traversing the connection alone (no other van besides him or
her) he or she is considered unsafe
Given that deposits have to reach the destination branch at the earliest
possible, drivers have to opt for the shortest route possible to reach the
destination. Operating under the aforementioned assumption choose the
connections in such a way that the number of drivers in unsafe conditions is
minimized & print the smallest number of drivers getting to unsafe state. |
T******e
发帖数: 157 | 7 听着挺有道理的，但具体怎么实现的呢？
删除那些作为前节点出现过的，但如何判断该不该删呢？
比如4个银行，3个司机去1，2，3
最短路径是这样：
0->1->2->3
0，1，2是前节点，1-3中剩3不是前节点，于是答案就是1
如果7个银行，3个司机去1，2，3
最短路径：
0->1->2->5->6->3->4
这个时候3也是一个前节点，但其实3是末尾，不能把它算到前节点里，这时候如何判断
？ |
Y*********d
发帖数: 47 | 8 0->1->2->5->6->3->4
我是这样实现的：
把1，2，3放入一个set A
从节点1循环到节点3
b = 当前节点的前节点
while b 不是NULL
把b的节点编号从A删除
b = b的前节点
A里剩下的应该都是末端节点的编号了，但结果还是比提供标准答案大，它提供的input
又很大，根本没办法把图画在纸上看看什么地方错了，自己试了几个小的input都对，
recruiter又催着要递交最终代码，真捉急啊 |
T******e
发帖数: 157 | 9 没发现有啥问题，那找最小路径也没啥问题吧应该
比如4个银行，2个司机
最小路径有：
0->3->1
0->2->1
这种情况也考虑了吧 |
Y*********d
发帖数: 47 | 10 这种有多个最短路程的情况先前的确没考虑，试了试把找末端代码改成把到各节点所有
可能的最短路程组合都看一遍，现在结果是都对了，但是有2个比较大的input超时了，
试了几个memoization优化也仍旧超时。这样看来要把所有可能的组合都试一遍似乎是
NP hard，有没有polynomial的算法啊。 |
T******e
发帖数: 157 | 11 可不可以在找最短路径、更新前节点的时候优先选择index小的点 |
c*******t
发帖数: 1095 | 12 难道不是BFS到K个银行构成的tree有多少个leaf吗？ klogk
为1
【在 Y*********d 的大作中提到】
: R个银行，index从0开始到R-1，K个司机，R >= K+1。司机全部从第0个银行开始同时出
: 发，目的地为index 1到K的银行。任意一个司机可以把index 1到K中任意一个银行作为
: 他的目的地。但是一个银行只能接纳一个司机，如果多个司机同时开到同一个index为1
: 至K中的一个银行，那么其中一个司机下车，其余司机继续开去其他目的地银行 。银行
: i 与银行 j 之间的路程长度用一个字符表示，'-'代表i和j不通，通的话这个字符会
: 是'1'至'9'之间的一个。每段路程是双向的，允许多个司机同时开。所有的司机都会选
: 最短的路程到达index 1到K的银行。如果任何一段路程在任意时间内只有一个司机在上
: 面开，那么那个司机就被认为是不安全行驶。在满足以上条件下，写程序算出最少能有
: 几个司机不安全行驶。
: Constraints
|
