#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int maxn = 1009;

double dp[maxn][maxn];
int d[maxn][maxn], deg[maxn], s[maxn][maxn], N, S, T;
bool inq[maxn], vis[maxn][maxn];
queue<int> q;

struct edge {
int to;
edge* next;
} E[maxn << 1], *pt = E, *head[maxn];

void AddEdge(int u, int v) {
deg[pt->to = v]++;
pt->next = head[u];
head[u] = pt++;
}

void Spfa(int d[], int S) {
for(int i = 0; i < N; i++)
d[i] = maxn, inq[i] = false;
d[S] = 0; inq[S] = true;
q.push(S);
while(!q.empty()) {
int x = q.front(); q.pop();
for(edge* e = head[x]; e; e = e->next) if(d[e->to] > d[x] + 1) {
d[e->to] = d[x] + 1;
if(!inq[e->to])
q.push(e->to), inq[e->to] = true;
}
}
}

void Init() {

int m;
scanf("%d%d%d%d", &N, &m, &S, &T); S--; T--;
memset(deg, 0, sizeof(int) * N);
while(m--) {
int u, v;
scanf("%d%d", &u, &v); u--; v--;
AddEdge(u, v);
AddEdge(v, u);
}

for(int i = 0; i < N; i++) Spfa(d[i], i);

memset(s, -1, sizeof s);

for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(edge* e = head[i]; e; e = e->next)if(d[i][j] == d[e->to][j] + 1) {
if(~s[i][j])
s[i][j] = min(s[i][j], e->to);
else
s[i][j] = e->to;
}

memset(vis, 0, sizeof vis);
for(int i = 0; i < N; i++) {
dp[i][i] = 0;
vis[i][i] = true;
for(int j = 0; j < N; j++)
if(i != j && ~s[i][j] && (s[i][j] == j || s[s[i][j]][j] ==j)) {
dp[i][j] = 1;
vis[i][j] = true;
}
}

}

double Dp(int x, int y) {
if(vis[x][y]) return dp[x][y];
vis[x][y] = true;

dp[x][y] = Dp(s[s[x][y]][y],y);
for(edge* e = head[y]; e; e = e->next)
dp[x][y] += Dp(s[s[x][y]][y],e->to);

return ++(dp[x][y] /= deg[y] + 1);
}

int main() {

Init();
printf("%.3lf\n", Dp(S, T));

return 0;
}

最短路+dp http://www.cnblogs.com/JSZX11556/p/5060538.html

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 21016 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 21020 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 21016 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 21016 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 21020 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 21020 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 21020 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 21020 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 21016 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 21020 KiB, score = 10
Accepted, time = 183 ms, mem = 21020 KiB, score = 100
用dp[s,t]表示聪聪在s，可可在t时聪聪吃到可可的期望。
dp方程程序里有。
其中p[s,t]表示聪聪在s点，可可在t点，聪聪走一步会走到哪里，自然p[p[s,t],t]就是聪聪走两步会走到哪里。p数组可以用SPFA预处理出来。

Block Code

#include <cstdio>
#include <cstring>
#define N 1005
#define M N*N

int h[N], nxt[M], to[M], cnt = 0;
int dis[N], p[N][N];
double dp[N][N];
bool v[N][N], vis[N];
int q[3*N], f, r;
int n, s, t;

void add(int u, int v) {
nxt[cnt] = h[u];
to[cnt] = v;
h[u] = cnt++;
}

void bfs(int s) {
memset(dis,127,sizeof(dis));
f = r = 0;
q[r++] = s;
dis[s] = 0;
p[s][s] = s;
vis[s] = 1;
while(f < r) {
int u = q[f++];
vis[u] = 0;
for(int i=h[u];i!=-1;i=nxt[i]) {
int v = to[i];
if(!vis[v] && dis[v]>dis[u]+1) {
dis[v]=dis[u]+1;
p[v][s] = u;
q[r++] = v;
vis[v] = 1;
} else if(dis[v]==dis[u]+1 && u<p[v][s]) {
p[v][s] = u;
}
}
}
}

double calc(int s, int t) {
if(s == t) return 0;
if(v[s][t]) return dp[s][t];
v[s][t] = 1;
if(p[s][t]==t || p[p[s][t]][t]==t) return dp[s][t] = 1;
dp[s][t] += calc(p[p[s][t]][t], t);
int k = 1;
for(int i=h[t];i!=-1;i=nxt[i]) {
dp[s][t] += calc(p[p[s][t]][t], to[i]);
k++;
}
return dp[s][t] = dp[s][t] / k + 1;
}

int main() {
freopen("cchkk.in","r",stdin);
freopen("cchkk.out","w",stdout);

int x, y, m;
memset(h,-1,sizeof(h));
memset(vis,0,sizeof(vis));

scanf("%d%d%d%d", &n, &m, &s, &t);
while(m--) {
scanf("%d%d", &x, &y);
add(x,y); add(y,x);
}
for(x = 1; x <= n; x++)
for(y = 1; y <= n; y++) {
dp[x][y] = 0.0;
v[x][y] = 0;
}
for(m = 1; m <= n; m++)
bfs(m);
printf("%.3lf", calc(s, t));

fclose(stdin); fclose(stdout);
return 0;
}

spfa预处理+DP
编译成功

测试数据 #0: Accepted, time = 7 ms, mem = 13256 KiB, score = 10
测试数据 #1: Accepted, time = 7 ms, mem = 13256 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 13256 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 13260 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 13256 KiB, score = 10
测试数据 #5: Accepted, time = 109 ms, mem = 13268 KiB, score = 10
测试数据 #6: Accepted, time = 140 ms, mem = 13268 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 13256 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 13256 KiB, score = 10
测试数据 #9: Accepted, time = 78 ms, mem = 13280 KiB, score = 10
Accepted, time = 447 ms, mem = 13280 KiB, score = 100

代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
#include <vector>

using namespace std ;

#define AddEdge( s , t ) e[ s ].pb( t ) , e[ t ].pb( s )
#define maxn 1010
#define pb push_back
#define pf push_front
#define inf 0x7fffffff
#define travel( s ) for ( vector < int > :: iterator p = e[ s ].begin( ) ; p != e[ s ].end( ) ; ++ p )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

vector < int > e[ maxn ] ;
int n , m , st , to , next[ maxn ][ maxn ] , d[ maxn ] ;

int dist[ maxn ] ;
deque < int > q ;
bool f[ maxn ] ;

void spfa( int S ) {
memset( f , false , sizeof( f ) ) , q.clear( ) ;
rep( i , n ) dist[ i ] = inf ;
dist[ S ] = 0 , f[ S ] = true , q.pf( S ) ;
while ( ! q.empty( ) ) {
int v = q.front( ) ; q.pop_front( ) , f[ v ] = false ;
travel( v ) if ( dist[ *p ] > dist[ v ] + 1 ) {
dist[ *p ] = dist[ v ] + 1 ;
if ( ! f[ *p ] ) {
f[ *p ] = true ;
if ( ! q.empty( ) && dist[ *p ] < dist[ q.front( ) ] ) q.pf( *p ) ; else q.pb( *p ) ;
}
}
}
}

double dp[ maxn ][ maxn ] ;
bool flag[ maxn ][ maxn ] ;

double Dp( int v , int u ) {
if ( flag[ v ][ u ] ) return dp[ v ][ u ] ;
if ( v == u ) {
dp[ v ][ u ] = 0 , flag[ v ][ u ] = true ;
return dp[ v ][ u ] ;
}
int k = next[ v ][ u ] ;
if ( k != u ) k = next[ k ][ u ] ;
dp[ v ][ u ] = 1 ;
if ( k != u ) {
travel( u ) dp[ v ][ u ] += Dp( k , *p ) / double( d[ u ] + 1 ) ;
dp[ v ][ u ] += Dp( k , u ) / double( d[ u ] + 1 ) ;
}
flag[ v ][ u ] = true ;
return dp[ v ][ u ] ;
}

int main( ) {
scanf( "%d%d" , &n , &m ) ;
scanf( "%d%d" , &st , &to ) ;
memset( d , 0 , sizeof( d ) ) ;
while ( m -- ) {
int s , t ; scanf( "%d%d" , &s , &t ) ; AddEdge( s , t ) ;
++ d[ s ] , ++ d[ t ] ;
}
memset( next , 0 , sizeof( next ) ) ;
rep( i , n ) {
spfa( i ) ;
rep( j , n ) travel( j ) if ( ! next[ j ][ i ] || dist[ *p ] < dist[ next[ j ][ i ] ] || ( dist[ *p ] == dist[ next[ j ][ i ] ] && *p < next[ j ][ i ] ) ) {
next[ j ][ i ] = *p ;
}
}
memset( flag , false , sizeof( flag ) ) ;
printf( "%.3f\n" , Dp( st , to ) ) ;
return 0 ;
}

WA了一次

提醒一下，聪聪是每回合分别做两次走一步决策，而不是做走两步的决策。

楼下神牛bsNOI的题，orz！！！！！！！！！

noip难度的noi题

ms题意不太清楚

哈哈哈哈哈哈

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

so difficult! - -||

。。第二十个

交了N次

通过率50%-->36%

第一个难度4的题

庆祝下

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

图论+DP

注意聪聪一次最多可以走两步！

平均！！

AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 88ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：232ms

sunny果然不错，conan最强……

我不会哦