GYM 101149 L. Right Build【最短路+思维】经典题

L. Right Build time limit per test 2.0 s memory limit per test 256 MB input standard input output standard 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 yjdepends 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

题目大意：

问从0出发，到a这个点和b这个点的总路径的最小值。

思路：

非常经典的一个最短路模型题。

我们首先跑一遍从0开始的单源最短路，设定为D【i】；

然后反向建图：

①跑一遍从a开始的单源最短路，设定为F【i】；

②跑一遍从b开始的单源最短路，设定为L【i】；

然后我们枚举一个重复路径点，使得同时维护D【i】+F【i】+L【i】的最小值即可。

Ac代码：

#include<stdio.h> #include<string.h> #include<vector> #include<queue> using namespace std; int xx[350000]; int yy[350000]; int vis[350000]; vector<int>mp[350000]; int dist[5][350000]; int n,m,A,B; void SPFA(int ss,int dd) { queue<int>s; s.push(ss); memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++)dist[dd][i]=0x3f3f3f3f; dist[dd][ss]=0; while(!s.empty()) { int u=s.front(); vis[u]=0; s.pop(); for(int i=0;i<mp[u].size();i++) { int v=mp[u][i]; if(dist[dd][v]>dist[dd][u]+1) { dist[dd][v]=dist[dd][u]+1; if(vis[v]==0) { vis[v]=1; s.push(v); } } } } } int main() { while(~scanf("%d%d%d%d",&n,&m,&A,&B)) { for(int i=1;i<=n;i++)mp[i].clear(); for(int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); mp[x].push_back(y); xx[i]=x;yy[i]=y; } int ans=0x3f3f3f3f; SPFA(0,0); for(int i=1;i<=n;i++)mp[i].clear(); for(int i=1;i<=m;i++) { int x=xx[i],y=yy[i]; mp[y].push_back(x); } SPFA(A,1); SPFA(B,2); for(int i=0;i<=n;i++) { if(dist[0][i]==0x3f3f3f3f||dist[1][i]==0x3f3f3f3f||dist[2][i]==0x3f3f3f3f)continue; ans=min(ans,dist[0][i]+dist[1][i]+dist[2][i]); } printf("%d\n",ans); } }