L.Right Build【古典的な最短問題、dijkstra+優先キュー】
6088 ワード
L. Right Build
time limit per test2.0 s memory limit per test256 MB inputstandard input outputstandard output
In a MMORPG «Path of Exile» characters grow by acquiring talents for special talent points received in a game process. Talents can depend on others. A talent can be acquired only if a character has at least one of the talents it depends on. Acquiring one talent costs one talent point. At the beginning of the game a character has a single starting talent.
Schoolboy Vasiliy decided to record a video manual how to level-up a character in a proper way, following which makes defeating other players and NPCs very easy. He numbered all talents as integers from 0 to n, so that the starting talent is numbered as 0. Vasiliy thinks that the only right build is acquiring two different talents a and b as quickly as possible because these talents are imbalanced and much stronger than any others. Vasiliy is lost in thought what minimal number of talent points is sufficient to acquire these talents from the start of the game.
Input
The first line contains four space-separated integers: n, m, a and b (2 ≤ n, m ≤ 2·105, 1 ≤ a, b ≤ n, a ≠ b) — the total number of talents, excluding the starting talent, the number of dependencies between talents, and the numbers of talents that must be acquired.
Each of the next m lines contains two space-separated integers: xj and yj (0 ≤ xj ≤ n, 1 ≤ yj ≤ n, xj ≠ yj), which means the talent yj depends on the talent xj. It’s guaranteed that it’s possible to acquire all talents given the infinite number of talent points.
Output
Output a single integer — the minimal number of talent points sufficient to acquire talents a and b.
Examples
input
6 8 4 6 0 1 0 2 1 2 1 5 2 3 2 4 3 6 5 6
output
4
input
4 6 3 4 0 1 0 2 1 3 2 4 3 4 4 3
output
3
これは泥棒のmengxiang 00000の問題で、確かにとても経典の問題で、みんなに問題をすることをお勧めします:あなたにn+1点、m辺をあげて、それからあなたに2つの点a,bをあげて、0点からa,b点の長さの総和を求めます.分析:この問題を一目で見れば最短になるが、手をつけることができない.大牛の分析を見てやっと分かったのは、まず0点の単源から最短になることを順方向に求め、それから逆方向に図を作り、a,bから出発した単源の最短になることを順に求め、最後に一つの中継点を列挙し、cを覚えておくことだ.答えは、dis[0->c]+dis[c->a]+dis[c->b]を繰り返してminを求めればよい
ツッコミ:この問題は探しにくいですね.vjで探したのは幸いです.
リファレンスコード
#includeint,int> > q;
q.push(make_pair(0,s));
while(!q.empty()){
int u = q.top().second;
q.pop();
for(int i = 0;i < e[u].size();i++){
int v = e[u][i];
if(dis[id][v] > dis[id][u] + 1){
dis[id][v] = dis[id][u] + 1;
q.push(make_pair(-dis[id][v],v));
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin>>n>>m>>a>>b;
init();
for(int i = 0;i < m;i++){
int x,y;cin>>x>>y;
aa[i] = x;bb[i] = y;
e[x].push_back(y);
}
dij(0,0);
init();
for(int i = 0;i < m;i++) e[bb[i]].push_back(aa[i]);//
dij(1,a);
dij(2,b);
int ans = 2000000000;
for(int i = 0;i <= n;i++)
ans = min(ans,dis[0][i]+dis[1][i]+dis[2][i]);
cout<return 0;
}