PKU演習問メモ(6/18)

No.	問題名	問題の種類および解法	難易度
1847	Tram	ダイクストラ法	★★☆☆☆

1847 Tram

問題概要

n個の交差点とそれらを結ぶ道路がある。
各交差点から出る道路、交差点の信号が最初に指している先の交差点が与えられる。

信号が指していない先の交差点に移動するには、信号を切り替える必要がある。
スタートの交差点からゴールの交差点に移動するのに必要な信号の切り替え回数の最小値を求めよ。

n≦100である。

解法

同じ交差点に2度来る必要がないことはすぐわかる。
（その交差点に最後に訪れたときに進んだ道に、最初から進めばよいから）

よってこれは、最初の信号が指している先の交差点は距離0,その他の交差点を距離1としたグラフを考え、Dijkstraのアルゴリズムで解くことができる。

ソースコード

int d[200][200];

int main()
{
	int n,a,b; cin>>n>>a>>b; a--,b--;
	rep(i,n)
	{
		fill_n(d[i],n,inf);
		
		int k; cin>>k;
		rep(j,k)
		{
			int t; cin>>t; t--;
			d[i][t]=j!=0;
		}
	}
	
	bool v[200];
	fill_n(v,n,0);
	priority_queue<pi> Q; Q.push(mp(0,a));
	
	while(!Q.empty())
	{
		int c=Q.top().second,cc=Q.top().first; Q.pop();
		
		if(v[c])continue;
		v[c]=1;
		if(c==b)
		{
			cout<<-cc<<endl; return 0;
		}
		
		rep(i,n)if(d[c][i]!=inf&&!v[i])Q.push(mp(cc-d[c][i],i));
	}
	cout<<-1<<endl;
	
	return 0;
}