thamcacphongban
quoc14
plain_text
5 months ago
11 kB
3
Indexable
caidat
10 10 0 9
1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 1 1
20 20 130 709
1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 1 1
10 18 0 100
1 1 0.33 1 2 0.67 2 2 0.82 2 3 0.18 3 3 0.52 3 4 0.48 4 4 0.83 4 5 0.17 5 5 0.0 5 6 1.0 6 6 0.15 6 7 0.85 7 7 0.4 7 8 0.6 8 8 0.03 8 9 0.97 9 9 0.76 9 10 0.24
10 19 249 1000
1 1 0.81 1 2 0.19 2 2 0.96 2 3 0.04 3 3 0.32 3 4 0.68 4 4 0.61 4 5 0.39 5 5 0.72 5 6 0.28 6 6 0.41 6 7 0.59 7 7 0.51 7 8 0.49 8 8 0.82 8 9 0.18 9 9 0.77 9 10 0.23 10 10 1
30 58 999 1000
8 8 0.14 21 21 0.74 2 2 0.58 1 2 0.26 3 4 0.02 12 13 0.43 6 7 0.52 16 17 0.85 20 20 0.87 25 25 0.36 2 3 0.42 26 27 0.73 20 21 0.13 4 5 0.48 12 12 0.57 9 10 0.81 6 6 0.48 1 1 0.74 3 3 0.98 28 28 0.69 23 23 0.05 10 11 0.86 10 10 0.14 25 26 0.64 21 22 0.26 5 5 0.37 28 29 0.31 17 18 0.28 11 11 0.95 15 15 0.48 26 26 0.27 17 17 0.72 18 18 0.89 11 12 0.05 13 14 0.8 9 9 0.19 8 9 0.86 19 20 0.97 15 16 0.52 24 24 0.15 13 13 0.2 29 30 0.25 22 22 0.82 18 19 0.11 27 27 0.42 16 16 0.15 4 4 0.52 27 28 0.58 22 23 0.18 29 29 0.75 19 19 0.03 7 7 0.81 24 25 0.85 14 15 0.8 23 24 0.95 7 8 0.19 5 6 0.63 14 14 0.2
50 99 741 1000
1 2 0.34 20 21 0.3 39 40 0.35 25 25 0.13 40 41 0.28 43 43 0.43 40 40 0.72 35 36 0.43 36 36 0.0 34 35 0.07 13 14 0.05 19 20 0.95 19 19 0.05 47 47 0.89 30 31 0.18 12 13 1.0 25 26 0.87 7 8 0.05 48 48 0.24 7 7 0.95 5 5 0.48 49 50 0.43 3 3 0.37 2 3 0.47 34 34 0.93 45 46 0.25 26 27 0.27 38 38 0.79 47 48 0.11 32 33 0.87 8 8 0.41 43 44 0.57 33 34 0.94 12 12 0.0 13 13 0.95 11 11 0.63 46 47 0.07 4 5 0.56 6 7 0.88 20 20 0.7 44 44 0.13 21 21 0.79 24 25 0.61 37 37 0.1 42 42 0.17 15 15 0.97 38 39 0.21 48 49 0.76 14 15 0.29 8 9 0.59 28 28 0.85 41 42 0.41 4 4 0.44 32 32 0.13 27 28 0.65 27 27 0.35 17 18 0.52 46 46 0.93 16 16 0.62 18 19 0.06 5 6 0.52 17 17 0.48 24 24 0.39 23 24 0.6 6 6 0.12 9 10 0.54 10 11 0.8 31 31 0.01 22 22 0.07 14 14 0.71 16 17 0.38 33 33 0.06 35 35 0.57 49 49 0.57 30 30 0.82 36 37 1.0 9 9 0.46 21 22 0.21 26 26 0.73 50 50 1 44 45 0.87 28 29 0.15 45 45 0.75 2 2 0.53 31 32 0.99 29 30 0.45 29 29 0.55 1 1 0.66 15 16 0.03 37 38 0.9 42 43 0.83 41 41 0.59 18 18 0.94 22 23 0.93 3 4 0.63 23 23 0.4 10 10 0.2 39 39 0.65 11 12 0.37
10 100 13 1000
1 1 0.07 1 2 0.13 1 3 0.1 1 4 0.12 1 5 0.08 1 6 0.1 1 7 0.11 1 8 0.11 1 9 0.05 1 10 0.13 2 1 0.08 2 2 0.11 2 3 0.09 2 4 0.13 2 5 0.08 2 6 0.12 2 7 0.09 2 8 0.11 2 9 0.11 2 10 0.08 3 1 0.07 3 2 0.11 3 3 0.15 3 4 0.07 3 5 0.1 3 6 0.11 3 7 0.08 3 8 0.13 3 9 0.08 3 10 0.1 4 1 0.1 4 2 0.18 4 3 0.06 4 4 0.11 4 5 0.09 4 6 0.11 4 7 0.06 4 8 0.1 4 9 0.09 4 10 0.1 5 1 0.09 5 2 0.13 5 3 0.13 5 4 0.09 5 5 0.11 5 6 0.07 5 7 0.08 5 8 0.05 5 9 0.12 5 10 0.13 6 1 0.13 6 2 0.06 6 3 0.07 6 4 0.14 6 5 0.08 6 6 0.15 6 7 0.13 6 8 0.1 6 9 0.05 6 10 0.09 7 1 0.11 7 2 0.14 7 3 0.08 7 4 0.09 7 5 0.06 7 6 0.13 7 7 0.1 7 8 0.11 7 9 0.1 7 10 0.08 8 1 0.06 8 2 0.08 8 3 0.04 8 4 0.12 8 5 0.12 8 6 0.1 8 7 0.12 8 8 0.1 8 9 0.06 8 10 0.2 9 1 0.15 9 2 0.11 9 3 0.09 9 4 0.14 9 5 0.03 9 6 0.06 9 7 0.08 9 8 0.1 9 9 0.12 9 10 0.12 10 1 0.08 10 2 0.03 10 3 0.07 10 4 0.16 10 5 0.1 10 6 0.13 10 7 0.15 10 8 0.08 10 9 0.07 10 10 0.13
10 100 242 1000
7 7 0.08 2 8 0.15 10 4 0.08 8 4 0.18 5 1 0.04 6 2 0.13 10 3 0.09 7 2 0.07 10 5 0.06 8 7 0.11 10 2 0.1 7 8 0.13 3 7 0.1 5 10 0.07 4 2 0.04 8 3 0.08 4 5 0.1 2 2 0.07 4 6 0.12 2 10 0.06 6 7 0.06 4 1 0.16 6 8 0.11 4 8 0.14 10 6 0.16 3 4 0.12 3 8 0.09 1 6 0.1 6 3 0.08 9 10 0.16 5 8 0.15 9 7 0.1 4 9 0.09 6 6 0.13 1 5 0.15 3 2 0.09 9 8 0.11 1 2 0.08 8 1 0.11 5 2 0.07 4 7 0.06 1 1 0.08 3 10 0.11 4 10 0.09 3 5 0.09 2 5 0.08 8 9 0.09 9 3 0.08 3 6 0.1 7 3 0.09 1 10 0.1 5 7 0.14 6 5 0.17 10 9 0.03 4 4 0.13 5 4 0.1 2 4 0.07 7 6 0.13 9 4 0.08 7 1 0.04 10 1 0.11 8 10 0.04 5 6 0.11 4 3 0.07 8 6 0.09 7 4 0.07 2 7 0.13 1 7 0.12 2 1 0.15 2 3 0.1 1 4 0.06 9 9 0.12 7 9 0.08 9 1 0.09 6 1 0.07 2 6 0.08 8 5 0.12 5 5 0.15 6 9 0.07 9 6 0.09 10 10 0.13 8 2 0.12 7 10 0.14 3 3 0.08 9 2 0.07 5 3 0.09 8 8 0.06 5 9 0.08 2 9 0.11 1 3 0.1 10 7 0.13 9 5 0.1 10 8 0.11 6 4 0.09 3 9 0.14 1 9 0.12 7 5 0.17 3 1 0.08 1 8 0.09 6 10 0.09
100 200 498 1000
58 57 0.25 86 85 0.77 93 92 0.71 71 72 0.64 68 67 0.16 95 94 0.34 45 44 0.97 92 91 0.64 89 90 0.28 11 12 0.62 37 36 0.36 24 23 0.69 65 66 0.52 13 12 0.47 20 21 0.53 46 47 0.15 19 18 0.2 24 25 0.31 41 40 0.51 79 80 0.47 17 16 0.76 44 43 0.2 69 68 0.64 9 8 0.31 22 23 0.86 91 90 0.32 35 34 0.95 78 79 0.91 64 63 0.98 42 43 0.52 81 80 0.32 39 38 0.46 85 86 0.02 7 6 0.7 29 28 0.37 49 48 0.33 20 19 0.47 2 3 0.53 3 4 0.75 100 99 0.08 26 25 0.47 88 87 0.56 53 54 0.55 98 99 0.01 74 73 0.65 68 69 0.84 23 22 0.59 81 82 0.68 28 27 0.26 54 53 0.73 62 63 0.2 9 10 0.69 76 77 0.18 83 84 0.35 72 73 0.21 25 24 0.83 42 41 0.48 74 75 0.35 61 62 0.84 26 27 0.53 75 76 0.86 84 85 0.57 71 70 0.36 66 67 0.86 75 74 0.14 82 83 0.71 63 64 0.63 59 58 0.78 83 82 0.65 2 1 0.47 40 41 0.96 23 24 0.41 62 61 0.8 78 77 0.09 30 31 0.51 55 56 0.62 29 30 0.63 34 33 0.54 87 88 0.27 25 26 0.17 3 2 0.25 69 70 0.36 52 51 0.21 88 89 0.44 51 50 0.11 63 62 0.37 50 49 0.62 31 30 0.9 8 7 0.56 21 20 0.67 77 76 0.52 41 42 0.49 46 45 0.85 37 38 0.64 32 33 0.22 27 26 0.75 50 51 0.38 60 61 0.18 4 5 0.07 18 17 0.07 79 78 0.53 55 54 0.38 94 93 0.93 60 59 0.82 17 18 0.24 97 98 0.91 61 60 0.16 97 96 0.09 96 95 0.8 73 72 0.06 85 84 0.98 16 15 0.31 48 49 0.45 43 44 1.0 100 1 0.92 90 89 0.95 54 55 0.27 39 40 0.54 84 83 0.43 47 46 0.53 32 31 0.78 48 47 0.55 19 20 0.8 66 65 0.14 1 100 0.03 27 28 0.25 47 48 0.47 96 97 0.2 21 22 0.33 80 79 0.49 80 81 0.51 30 29 0.49 12 11 0.39 36 35 0.06 7 8 0.3 16 17 0.69 5 6 0.71 33 32 0.65 82 81 0.29 11 10 0.38 15 14 0.44 67 68 0.96 57 56 0.44 70 69 0.17 5 4 0.29 45 46 0.03 99 98 0.83 70 71 0.83 57 58 0.56 8 9 0.44 94 95 0.07 98 97 0.99 13 14 0.53 34 35 0.46 53 52 0.45 4 3 0.93 52 53 0.79 86 87 0.23 6 7 0.26 87 86 0.73 73 74 0.94 33 34 0.35 38 39 0.94 58 59 0.75 36 37 0.94 28 29 0.74 51 52 0.89 14 13 0.03 59 60 0.22 89 88 0.72 31 32 0.1 92 93 0.36 64 65 0.02 1 2 0.97 95 96 0.66 12 13 0.61 76 75 0.82 18 19 0.93 38 37 0.06 93 94 0.29 99 100 0.17 10 9 0.55 43 42 0.0 15 16 0.56 44 45 0.8 22 21 0.14 65 64 0.48 90 91 0.05 56 57 0.43 77 78 0.48 35 36 0.05 72 71 0.79 14 15 0.97 49 50 0.67 56 55 0.57 6 5 0.74 10 11 0.45 91 92 0.68 40 39 0.04 67 66 0.04
100 200 802 1000
15 16 0.79 84 83 0.45 49 50 0.93 76 77 0.8 36 35 0.21 77 76 0.8 7 6 0.74 10 9 0.42 51 52 0.99 14 15 0.55 41 42 0.44 79 78 0.73 13 12 0.52 42 43 0.2 82 83 0.62 74 75 0.74 62 61 0.25 96 95 0.25 29 30 0.35 53 54 0.88 52 51 0.01 50 49 0.07 79 80 0.27 39 38 0.0 9 10 0.31 19 18 0.21 27 28 0.51 97 98 0.67 57 58 0.18 88 87 0.73 83 84 0.6 77 78 0.2 53 52 0.12 66 67 0.91 49 48 0.07 3 2 0.47 89 88 0.11 22 21 0.79 64 63 0.17 22 23 0.21 43 44 0.96 37 38 0.81 87 88 0.64 70 71 0.43 11 10 0.67 76 75 0.2 54 55 0.43 18 17 0.85 56 57 0.24 46 45 0.18 93 92 0.8 69 70 0.9 78 79 0.73 60 59 0.67 71 72 0.84 16 15 0.92 58 59 0.54 47 46 0.97 45 46 0.18 52 53 0.99 32 31 0.8 99 98 0.82 56 55 0.76 23 22 0.82 35 34 0.77 24 25 0.15 8 7 0.34 54 53 0.57 46 47 0.82 51 50 0.01 4 3 0.16 91 90 0.65 9 8 0.69 30 31 0.21 11 12 0.33 43 42 0.04 6 7 0.92 20 19 0.37 61 62 0.51 89 90 0.89 7 8 0.26 29 28 0.65 44 43 0.38 59 58 0.26 80 81 0.54 75 74 0.93 37 36 0.19 90 89 0.61 23 24 0.18 73 74 0.9 25 24 0.41 17 16 0.34 10 11 0.58 84 85 0.55 94 95 0.55 27 26 0.49 8 9 0.66 32 33 0.2 66 65 0.09 57 56 0.82 26 27 0.11 61 60 0.49 90 91 0.39 68 69 0.38 18 19 0.15 97 96 0.33 72 71 0.75 94 93 0.45 34 33 0.83 33 32 0.6 78 77 0.27 63 64 0.93 5 6 0.4 80 79 0.46 48 49 0.03 58 57 0.46 64 65 0.83 63 62 0.07 82 81 0.38 100 1 0.58 99 100 0.18 2 1 0.41 88 89 0.27 24 23 0.85 92 91 0.57 62 63 0.75 55 56 0.52 28 29 0.5 12 13 0.27 38 37 0.81 65 64 0.49 1 100 0.36 83 82 0.4 45 44 0.82 31 32 0.33 96 97 0.75 42 41 0.8 73 72 0.1 21 22 0.3 4 5 0.84 98 99 0.6 30 29 0.79 14 13 0.45 41 40 0.56 91 92 0.35 85 86 0.52 85 84 0.48 34 35 0.17 100 99 0.42 31 30 0.67 70 69 0.57 87 86 0.36 28 27 0.5 81 82 0.41 44 45 0.62 50 51 0.93 1 2 0.64 67 66 0.95 35 36 0.23 86 85 0.99 75 76 0.07 93 94 0.2 3 4 0.53 67 68 0.05 47 48 0.03 55 54 0.48 95 94 0.54 38 39 0.19 5 4 0.6 21 20 0.7 68 67 0.62 65 66 0.51 40 41 0.07 2 3 0.59 19 20 0.79 86 87 0.01 17 18 0.66 15 14 0.21 40 39 0.93 69 68 0.1 95 96 0.46 13 14 0.48 59 60 0.74 20 21 0.63 36 37 0.79 98 97 0.4 12 11 0.73 81 80 0.59 72 73 0.25 26 25 0.89 74 73 0.26 92 93 0.43 25 26 0.59 39 40 1.0 33 34 0.4 6 5 0.08 60 61 0.33 71 70 0.16 16 17 0.08 48 47 0.97
#1 1 1.000000 1 1.000000
#2 11 1.000000 18 1.000000
#3 4 0.386860 4 0.386860
#4 10 0.946340 10 0.851171
#5 3 0.150855 1 1.000000
#6 15 0.284926 7 0.505935
#7 4 0.118507 4 0.118507
#8 5 0.121474 5 0.121474
#9 3 0.591954 3 0.637576
#10 7 0.314579 6 0.280350
#include <iostream>
using namespace std;
// ma tran ke
struct custom{
short arr[100];
float ss[100];
int size;
};
struct typeres{
int node;
float ss;
};
custom mtk[1002];
int sizee(int node)
{
return mtk[node].size;
}
void pushh(int node, int v, float xsuat)
{
mtk[node].arr[++mtk[node].size] = v;
mtk[node].ss[mtk[node].size] = xsuat;
}
int pullNode(int node, int pos)
{
return mtk[node].arr[pos];
}
float pullSS(int node, int pos)
{
return mtk[node].ss[pos];
}
void resetmtk()
{
for (int i = 0; i<=1000; i++)
mtk[i].size = 0;
}
// khai bao
int N, E, K, T;
float value[1002][1002];
typeres goo(int index, int mintime, int maxtime, int target)
{
for (int i = 1; i <= N; i++)
value[index+1][i] = 0;
if (target >= mintime && target <= maxtime)
{
// tim kiet qua tra ve
int anspos = 0;
float maxsx = 0;
for (int i = 1; i <= N; i++)
if (value[index][i] > maxsx)
{
maxsx = value[index][i];
anspos = i;
}
typeres tmpans;
tmpans.node = anspos;
tmpans.ss = maxsx;
return tmpans;
}
// tinh toan xacsuat cho luot di tiep theo
for (int i = 1; i <= N; i++)
if (value[index][i] != 0)
{
int nn = sizee(i);
for (int j = 1; j <= nn; j++)
{
int node = pullNode(i,j);
float sx = pullSS(i,j);
value[index+1][node] += value[index][i] * sx;
}
}
return goo(index + 1, maxtime + 1, maxtime + 10, target);
}
int main()
{
//freopen("input.txt","r",stdin);
int ntc;
//cin >> ntc;
for (int tc=1; tc<=10; tc++)
{
cin >> N >> E >> K >> T;
resetmtk();
for (int i = 1; i <= E; i++)
{
int u, v;
float xsuat;
cin >> u >> v >> xsuat;
pushh(u, v, xsuat);
}
value[1][1] = 1;
typeres tmp = goo(1,0, 9, T);
typeres tmp1 = goo(1,K, K+9, T);
cout.setf(ios::fixed);
cout.precision(6);
cout << "#"<<tc <<" ";
cout << tmp.node << " "<< tmp.ss << " "<<tmp1.node << " "<< tmp1.ss;
cout << endl;
}
return 0;
}
Leave a Comment