21 Days Training // Day 11

T1.

My idea : still enum.

Search all possible paths, and find the one with the mininum variance.

Code :

#include <bits/stdc++.h>
using namespace std;

struct queue_term {
    int nd=0;
    double sqsum=0, sum=0, L=0;
};

int main() {
    freopen("library.in", "r", stdin);
    freopen("library.out", "w", stdout);
    int N, M;cin >> N >> M;
    map<int, map<int, double> > G;
    for (int i=0;i<M;i++) {
        int u, v;
        double w;cin >> u >> v >> w;
        u--;v--;
        if (G.find(u)==G.end()) G[u] = map<int, double>();
        G[u][v] = w;
    }
    double var=998244353;
    queue<queue_term> Q;
    queue_term Qt={0,0,0,0};
    Q.push(Qt);
    while (!Q.empty()) {
        queue_term C=Q.front();
        Q.pop();
        if (C.nd==N-1) var = min(var, ((C.sqsum)/C.L)-(C.sum*C.sum)/(C.L*C.L));
        for (map<int, double>::iterator it=G[C.nd].begin();it!=G[C.nd].end();it++) {
            int nxt=(*it).first;
            double w=(*it).second;
            queue_term Qtx={nxt, C.sqsum+w*w, C.sum+w, C.L+1};
            Q.push(Qtx);
        }
    }
    printf("%.4lf", var);
    return 0;
}

Constraints :

Expected : 0(40)/30