Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <memory.h>
- #include <cstdlib>
- #include <algorithm>
- #include <iostream>
- #include <utility>
- #include <vector>
- #include <set>
- #include <map>
- #include <cmath>
- #include <string>
- #include <ctime>
- using namespace std;
- #define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
- #define pb push_back
- #define mp make_pair
- #define sz(a) (int)((a).size())
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> pii;
- const ld eps = 1e-10;
- int n, kp, path[510];
- vector<int> g[510];
- ld a[510][510];
- int id[510];
- ld p[510], np[510];
- bool gg[510][510];
- int main()
- {
- freopen( "in.txt", "r", stdin );
- freopen( "out.txt", "w", stdout );
- scanf( "%d", &n );
- scanf( "%d", &kp );
- forn( i, kp ) scanf( "%d", &path[i] );
- forn( i, n )
- {
- int k, x;
- scanf( "%d", &k );
- forn( j, k )
- {
- scanf( "%d", &x );
- g[i].pb( x );
- gg[i][x] = 1;
- }
- }
- forn( i, n )
- {
- forn( j, g[i].size() )
- a[ g[i][j] ][i] = 1.0 / g[i].size();
- a[i][i] -= 1.0;
- }
- forn( i, n ) a[n-1][i] = 1.0;
- a[n-1][n] = 1.0;
- /*
- forn( i, n )
- {
- forn( j, n+1 ) printf( "%.3f ", (double)a[i][j] );
- printf( "\n" );
- }
- */
- forn( i, n ) id[i] = i;
- int N = n+1;
- forn( i, n )
- {
- int j;
- for ( j=i; j<n; j++ )
- if ( fabs( a[ id[j] ][i] ) > eps ) break;
- swap( id[i], id[j] );
- for ( j=i+1; j<n; j++ )
- {
- ld coeff = -a[ id[j] ][i] / a[ id[i] ][i];
- for ( int q=i; q<N; q++ ) a[ id[j] ][q] += coeff * a[ id[i] ][q];
- }
- }
- for ( int i=n-1; i>=0; i-- )
- {
- p[ id[i] ] = a[ id[i] ][n];
- for ( int j=i+1; j<n; j++ ) p[ id[i] ] -= p[ id[j] ] * a[ id[i] ][j];
- p[ id[i] ] /= a[ id[i] ][i];
- }
- // forn( i, n ) printf( "%.3f ", (double)p[i] ); printf( "\n" );
- forn( i, kp )
- {
- p[ path[i] ] = 0;
- if ( i < kp-1 )
- {
- forn( j, n ) np[j] = 0;
- forn( j, n )
- forn( q, g[j].size() )
- if ( j != path[i+1] || g[j][q] != path[i] )
- np[ g[j][q] ] += p[j] / g[j].size();
- forn( j, n ) p[j] = np[j];
- }
- }
- ld ans = 0;
- forn( j, n ) ans += p[j];
- printf( "%.10f\n", double(ans) );
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement