Problem 1058 : Winter Bells

問題概要

日本語なので本文参照
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1058&lang=jp）

解法

やらなければいけないのは、Dijkstra+最短路における、そこまでの経路の数および、そこからゴールまでの経路の数のカウント。

まずは一度Dijkstraして各頂点までの最短距離を求めておく。
次に、各頂点からゴールまでの経路の数は、ゴールから逆にDijkstraして、次の頂点に現在の頂点までの経路の数を足していくDPをすれば求まる。

最後にサンタが通る確率を求める。サンタは全ての経路を等確率で通ることに注意する。
もう一度スタートからDijkstraして、次のノードに、(自分の確率)*(次のノードからゴールへ行く場合の数)/(自分からゴールへ行く場合の数)を足していくDPをすればよい。

ソースコード

int n,m,p,C[100];
vector<vector<pair<int,int> > > e;
int d[100];
bool v[100],u[100];
double togoal[100],prob[100];

int main(){
	while(cin>>n>>m>>p,n){
		e.clear(); e.resize(n);
		rep(i,m){
			int a,b,c; cin>>a>>b>>c;
			e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
		}
		rep(i,p)cin>>C[i];
		
		rep(i,n)d[i]=1<<28; d[0]=0;
		priority_queue<pair<int,int> > Q; Q.push(mp(0,0));
		while(!Q.empty()){
			int c=Q.top().second,cc=Q.top().first; Q.pop();
			if(c==n-1)break;
			if(d[c]<-cc)continue;
			fr(i,e[c])if(d[i->first]>-cc+i->second)
			d[i->first]=-cc+i->second,Q.push(mp(cc-i->second,i->first));
		}
		
		rep(i,n)u[i]=v[i]=0;
		rep(i,n)prob[i]=0,togoal[i]=0;
		togoal[n-1]=1; v[n-1]=1;
		Q=priority_queue<pair<int,int> >(); Q.push(mp(d[n-1],n-1));
		while(!Q.empty()){
			int c=Q.top().second; Q.pop();
			fr(i,e[c])if(d[i->first]+i->second==d[c]){
				togoal[i->first]+=togoal[c];
				if(!v[i->first])v[i->first]=1,Q.push(mp(d[i->first],i->first));
			}
		}
		Q=priority_queue<pair<int,int> >(); Q.push(mp(0,0));
		prob[0]=1; u[0]=1;
		while(!Q.empty()){
			int c=Q.top().second; Q.pop();
			fr(i,e[c])if(v[i->first]&&d[i->first]==d[c]+i->second)
			{
				prob[i->first]+=prob[c]*togoal[i->first]/togoal[c];
				if(!u[i->first])u[i->first]=1,Q.push(mp(-d[i->first],i->first));
			}
		}
		rep(i,p)printf("%.7f\n",prob[C[i]]); puts("");
	}
	return 0;
}