cf_g.cpp

//http://codeforces.com/gym/100371/attachments/download/2258/2014-zimnyaya-shkola-po-programmirovaniu-harkov-dyen-1-ye-kapun-vysshaya-liga-ru.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
typedef long double ldouble;

typedef pair<lint, int> E; 
int n;
vector<vector<E>> adj; // weight, vtx
vector< vector<int> > parents;

void findShortestPath() {
    vector<lint> cost(n, numeric_limits<lint>::max());
    set< E > q;
    parents.resize(n);
    q.insert(make_pair(0, 0));
    cost[0] = 0;
    while (!q.empty()) {
        auto u = q.begin()->second;
        q.erase(q.begin());
        for (auto v: adj[u]) {
			assert(v.second < adj.size());
            if (cost[v.second] > cost[u] + v.first) {
                q.erase( make_pair(cost[v.second], v.second) );
                cost[v.second] = cost[u] + v.first;
                parents[v.second].clear();
				parents[v.second].push_back(u); // erase old list of parents
                q.insert( make_pair(cost[v.second], v.second) );
            } else if (cost[v.second] == cost[u] + v.first) {
                parents[v.second].push_back(u); // add another parent
            }
        }
    }
}


// number of pathes with start at 0 and finish at i
// since graph of parents is reverse to the original traverse,
// count end traverse is actually countStart traverse in orignal graph
// and vise-versa
int dfsCount(int v, vector<int>& cnt, const vector<vector<int>>& next) {
    if (cnt[v] != -1)
        return cnt[v];
    cnt[v] = 0;
    for (auto u : next[v])
        cnt[v] += dfsCount(u, cnt, next);

    return cnt[v];
}

vector< vector<int> > children;
void buildReverse() {
	children.resize(n);
	for (int u = 0; u < n; ++u)
		for (auto v : parents[u])	
			children[v].push_back(u);
}


int main(int, char**) {
    std::ios::sync_with_stdio(false);
    int m;
    cin >> n >> m;
    adj.resize(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;

        cin >> u >> v >> w;
        --u; --v;
        adj[u].push_back( make_pair(w, v) );
        adj[v].push_back( make_pair(w, u) );
    }
    findShortestPath();
    
	vector<int> cntEnd(n, -1);	    
    cntEnd[0] = 1;
    dfsCount(n-1, cntEnd, parents);
	
	// build reverse graph to parent and using it compute cntEnd
	buildReverse();

	vector<int> cntStart(n, -1);
	cntStart[n-1] = 1;
	dfsCount(0, cntStart, children);

	// #N pathes is end(i)*start(i)
	double total = cntStart[0];
	for (int i = 0; i < n; ++i)
        cout << 2*(cntEnd[i]*1LL*cntStart[i])/total << " ";
    cout << endl;
	
	
	return 0;
}