有向树的叶到根的最短距离
这是我遇到的一个非常有趣的问题:有一个有向树，其中每个节点的权重随着时间变化，我必须找出从根到某个节点的距离。
问题陈述：
- 售票柜台前排起了长队。这里是队列considerations.
- There可以是最多2个传入队列在一个交叉点合并从任何交叉点只能有一个传出队列
- 可以有多个交汇点&队列移动
- 将只有一个最终票证计数器点所有队列都指向该点有多个入口点供风扇到达柜台
- 我需要设计一个系统，该系统可以向粉丝建议到达柜台的“最佳路径”及其“预期时间”
<>F217>
从队列到达柜台的预期时间取决于该队列中的人数加上其他队列中的人数。
假设有一个警察站在每个交叉口，他的工作是打开交叉口，把人从入队送到出队。
- 假设每个交叉口都有一名警察。如果交叉口有多个入队列，警察将从每个队列逐个发送风扇alternatively
例如，如果有2个入队队列，每个队列包含3个粉丝，则将首先发送来自queue1的领导人员，然后是来自queue2的领导人员，然后是来自queue1的下一个人员，依此类推。这是传入队列之间的另一种选择。
对于给定的输入
第一行包含队列的数量，第二行包含队列的数量，接下来的'e‘行包含三个值: junctions
- The
- ，
- 和队列中的人数。(这也是此队列中可以站立的最大人数。)
计算即将进入任何队列的人到达售票处的minimum time。此外，在最坏的情况下，输出他应该在最短时间内到达计数器的路径(在每个交叉点，警察开始从队列中选择人员，而不是我们正在计算的最小时间)。
如何解决这种时变问题？
例如：
7
6
1 5 9
2 5 5
3 6 1
4 6 3
5 7 7
6 7 4Graph如下所示：
售票柜台:7
入口点: 1，2，3，4
- 刚从入口点3进入队列的人所需的时间:队列(3，6)中的1人+队列(4，6)中的2人+队列(6，7)中的4人+队列(5，7)中的7人+队列(1，5)中的1人将走在此人之前。
最佳时间= 15
路径为3 -> 6 -> 7
回答 2
Stack Overflow用户
发布于 2016-08-28 20:23:39
这个问题可以通过寻找从每个入口节点(叶子)到出口节点(根)的最短路径来解决。
在下面的实现中，我使用邻接矩阵来表示这种(有向)图，但您可以将其视为二叉树(因为该问题为每个连接点定义了最多2个输入队列)。
伪码
int shortestPath(root)
if (both childs exists)
return min(shortestPath(node->left),shortestPath(node->right))*2+1
if (left child exists)
return shortestPath(node->left)
if (right child exists)
return shortestPath(node->right)
return 0; //no childs正常最短路径和这个问题之间的唯一区别是，每当我们有两个传入队列时，警察就会逐个交替地从每个队列中发送风扇。这意味着为了通过该队列，它将花费两倍的时间+1。+1是因为我们假设他从更长的队列路径开始。
C++代码
下面是一个有效的C++代码，它返回一个同时具有最佳时间和路径的对。如果有多条最优路径，它将只返回其中的一条。
const pair<int,vector<int>>& min(const pair<int,vector<int>>& a, const pair<int,vector<int>>& b) {
return (a.first < b.first) ? a : b;
}
pair<int,vector<int>> findShortestPath(vector<vector<int>>& graph, int v){
vector<pair<int,vector<int>>> childs;
for (int i=0; i<v; i++){
if (graph[i][v] != -1){
pair<int,vector<int>> path = findShortestPath(graph,i);
path.second.push_back(v+1);
childs.push_back(make_pair(path.first + graph[i][v], path.second));
}
}
if (childs.size() == 2){
pair<int,vector<int>> path = min(childs[0],childs[1]);
return make_pair(path.first*2+1, path.second);
}
if (childs.size() == 1){
return make_pair(childs[0].first,childs[0].second);
}
else{
vector<int> start = {v+1};
return make_pair(0,start);
}
}这段代码的时间复杂度是O(n^2)，其中n是顶点的数量。您也可以使用邻接表表示法(=二叉树)在O(n)中实现它。
为了完整起见，这里也是用于从给定输入创建图形并打印最佳时间和路径的main。See this live test of your example's input
int main()
{
int n, e;
cin >> n; //num of vertices
cin >> e; //num of queues
vector<vector<int>> graph;
//initialize graph matrix cells to -1
graph.resize(n);
for (int i=0;i<n;i++){
graph[i].resize(n);
for (int j=0;j<n;j++)
graph[i][j] = -1;
}
//add edges and their weights
for (int i=0;i<e;i++){
int s,d,val;
cin >> s >> d >> val;
graph[s-1][d-1] = val;
}
//run algorithm
pair<int,vector<int>> path = findShortestPath(graph, n-1);
//print results
cout << path.first << endl;
for (int i=0;i<path.second.size()-1;i++)
cout << path.second[i] << " -> ";
cout << path.second[path.second.size()-1] << endl;
return 0;
}Stack Overflow用户
发布于 2016-08-26 20:59:41
这应该通过动态编程来解决。
假设P( j )是人通过连接点j的位置，如果需要最佳风扇的话。例如，在你的例子中P(6) =4，因为到达连接点3的人将是第四个通过连接点6的人(在P27，P26和P28之后)。
以下三个命题是显而易见的，并解决了这个问题。
如果“连接点”j是风扇，则P(j) =1(基本情况)
如果“连接点”j是具有子对象l和r的真连接点，并且l和j之间的队列中有x人，r和j之间的队列中有y人，则我们有P(j) =2* min( P(l) +x，P(r) + y)。
如果有人要去柜台，需要n-1个时间。
你可以使用DP很容易地得到时间，并且通过一些记账(如果最小值在左边或右边)，你可以得到哪个是最优的风扇。
https://stackoverflow.com/questions/39137294
复制相似问题
腾讯云开发者
