首页 > 代码库 > Codeforces gym Hello 2015 Div1 B and Div2 D
Codeforces gym Hello 2015 Div1 B and Div2 D
Codeforces gym Hello 2015 Div1 B and Div2 D
Codeforces gym 100571 problem D
Problem
给一个有向图G<V，E>和源点S，边的属性有长度L和颜色C，即E=<L，C>。进行Q次询问，每次给定一个点X，输出S到X的最短路的长度（不存在则输出 -1）。但要求S到X的路径中相邻两条边颜色不一样。
Limits
Time Limit(ms): 1000
Memory Limit(MB): 256
|V|, |E|: [1, 10^5]
X, S: [1, |V| ]
L: [1, 10^9]
|C|: [1, 10^5]
Q: [1, 10^5]
Solution
设V=<minlen，mincolor，secondlen，secondcolor>；minlen表示到点v的最短路长度，mincolor表示最短路最后一条边的颜色，secondlen表示到点v的次短路长度，secondcolor表示次短路最后一条边的颜色。注意，要保证任何时刻mincolor与secondcolor不同。用SPFA算法，初始时源点加入队列，每次从队列中取点，往能到达的所有点更新，并适当将点加入队列。设e为当前边，now为当前点，to为待更新点；若now的mincolor与e的颜色不同，则用now的最小边更新，否则用now的次小边更新（如果存在）；直到队列为空，则求出了源点S到所有点的最短路长度。
More
不失一般性，假设当前用now的最小边更新，若now.minlen+e.len<to.minlen，则更新to的最小边，但注意此时可能需要将to的最小边替代to的次小边，前提是e.color与to.mincolor不同；若now.minlen+e.len>=to.minlen 且 now.minlen+e.len<to.secondlen，则更新to的次小边，但前提是e.color与to.mincolor不同。更新边len的同时更新color。用now的次小边更新时类似于用now的最小边更新，但前提是now的次小边存在。每次更新了to，若to不在队列中，则加入队列。
Complexity
Time Complexity: O(k*|E|) （k不大）
Memory Complexity: O(|V|+|E|)
Source
Codeforces gym Hello 2015 Div1 B and Div2 D
Code
Codeforces gym Hello 2015 Div1 B and Div2 D From My Github
Codeforces gym Hello 2015 Div1 B and Div2 D
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。