- #include#include#include#include#include using namespace std;
- typedef long long ll;
- const int N = 1005;
- inline int read() {
- char c = getchar();
- int x = 0,
- f = 1;
- while (c < '0' || c > '9') {
- if (c == ' - ') f = -1;
- c = getchar();
- }
- while (c >= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- int n,
- m,
- a,
- b,
- de[N],
- u,
- v;
- struct edge {
- int v,
- ne;
- }
- e[N << 1];
- int h[N],
- cnt;
- inline void ins(int u, int v) {
- cnt++;
- e[cnt].v = v;
- e[cnt].ne = h[u];
- h[u] = cnt;
- cnt++;
- e[cnt].v = u;
- e[cnt].ne = h[v];
- h[v] = cnt;
- }
- int g[N][N];
- int q[N],
- head,
- tail,
- d[N][N];
- bool inq[N];
- inline void lop(int & x) {
- if (x == N) x = 1;
- }
- void bfs(int s, int * g, int * d) {
- head = tail = 1;
- memset(inq, 0, sizeof(inq));
- q[tail++] = s;
- d[s] = 0;
- inq[s] = 1;
- while (head != tail) {
- int u = q[head++];
- inq[u] = 0;
- lop(head);
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (d[v] > d[u] + 1 || (d[v] == d[u] + 1 && g[v] > g[u])) {
- d[v] = d[u] + 1;
- g[v] = g[u] == 0 ? v: g[u];
- if (!inq[v]) q[tail++] = v,
- inq[v] = 1,
- lop(tail);
- }
- }
- }
- }
- double f[N][N];
- double dfs(int a, int b) { //printf("dfs %d %d\n",a,b);
- if (a == b) return 0;
- if (g[a][b] == b || g[g[a][b]][b] == b) return 1;
- if (f[a][b]) return f[a][b];
- double & re = f[a][b];
- int t = g[g[a][b]][b];
- re = dfs(t, b);
- for (int i = h[b]; i; i = e[i].ne) re += dfs(t, e[i].v);
- re = re / (de[b] + 1) + 1;
- return re;
- }
- int main() {
- freopen("in", "r", stdin);
- n = read();
- m = read();
- a = read();
- b = read();
- for (int i = 1; i <= m; i++) u = read(),
- v = read(),
- de[u]++,
- de[v]++,
- ins(u, v);
- memset(d, 127, sizeof(d));
- for (int i = 1; i <= n; i++) bfs(i, g[i], d[i]);
- //for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("g %d %d %d\n",i,j,g[i][j]);
- printf("%.3lf", dfs(a, b));
- }
来源: http://www.bubuko.com/infodetail-1970049.html