結果

問題 No.298 話の伝達
コンテスト
ユーザー paruki
提出日時 2016-04-20 07:20:45
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,950 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,402 ms
コンパイル使用メモリ 170,772 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-04 14:17:50
合計ジャッジ時間 2,366 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include "bits/stdc++.h"
using namespace std;
#define rt return
#define FOR(i,j,k) for(int i=j; i<(int)k;++i)
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

typedef double Weight;
struct Edge{
    int from, to;
    Weight wei;
    Edge(int from_, int to_, Weight wei_):from(from_),to(to_),wei(wei_){}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

class TopologicalSort{
public:
    vi operator()(const Graph &G){
        vis = vi((int)G.size());
        hasCycle = 0;
        rep(i, G.size()){
            dfs(G, i);
            if(hasCycle) return vi();
        }
        reverse(all(res));
        return move(res);
    }
private:
    vi vis, res;
    bool hasCycle;

    void dfs(const Graph &G, int v){
        if(vis[v] == 1)
            hasCycle = 1;
        if(vis[v]) return;
        vis[v] = 1;
        for(const Edge &edge: G[v])
            dfs(G, edge.to);
        vis[v] = 2;
        res.push_back(v);
    }
};

Graph makeWDGraph(int V, const vector<int> &from, const vector<int> &to, const vector<Weight> &wei){
    Graph G(V);
    int E = (int)from.size();
    for(int i=0;i<E;++i)G[from[i]].emplace_back(from[i],to[i],wei[i]);
    return G;
}

double p[20];

int main(){
    int N, M;
    cin >> N >> M;
    vi A(M), B(M);
    vector<double> C(M);
    rep(i, M){
        cin >> A[i] >> B[i] >> C[i];
        C[i] *= 0.01;
    }
    Graph G = makeWDGraph(N, A, B, C);
    vi vers = TopologicalSort()(G);
    p[0] = 1;
    each(v, vers){
        each(e, G[v]){
            p[e.to] += (1 - p[e.to])*e.wei*p[v];
        }
    }
    printf("%0.20f\n", p[N - 1]);
}
0