#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
using namespace std;
#define EPS 1e-9
vector<int> adj[33];
vector<int> wht[33];
int in[33],out[33];
int n,m;
double a[33][33],b[33];
void gauss() {
for(int i=0;i<=n;++i) {
double mx = 0; int idx = -1;
for(int j=i;j<=n;++j) if(abs(a[j][i]) > mx) {
mx = abs(a[j][i]);
idx = j;
}
for(int j=0;j<=n;++j) swap(a[i][j],a[idx][j]);
swap(b[i],b[idx]);
double tt = a[i][i];
for(int k=i;k<=n;++k) a[i][k] /= tt;
b[i] /= tt;
for(int j=0;j<=n;++j) if(j != i && abs(a[j][i]) > EPS) {
double tmp = a[j][i];
for(int k=0;k<=n;++k) {
a[j][k] -= tmp * a[i][k];
} b[j] -= tmp * b[i];
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i) {
int u,v,w; scanf("%d%d%d",&u,&v,&w);
adj[u].push_back(v);
wht[u].push_back(w);
out[u]++, in[v]++;
}
for(int u=0;u<=n;++u) {
a[u][u] = 1;
for(int i=0;i<adj[u].size();++i) {
int v = adj[u][i];
int w = wht[u][i];
a[u][v] += -1.0/out[u];
b[u] += 1.0 * w / out[u];
}
}
gauss();
printf("%.10lf",b[0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1684 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1684 KB |
Output is correct |
