Codeforces 59 E. Shortest Path

問題

n個の都市と、それらをつなぐm本の道がある。
1番の都市からn番の都市へ、使う数の道を最小にして移動したい。

ただし、決められた都市の組(a[i],b[i],c[i])がいくつかあり、
それらをこの順に通ることはできない。

n番の都市へ、使う道の本数を最小にしたときの、訪れる都市を順に出力せよ。
複数ある場合どれを出力してもかまわない。

制約条件

n≦3000
m≦20000
都市の組≦10^5

方針

幅優先探索+経路復元。
ただし、状態として今居る都市ではなく、最後に使った辺を持っておく。
これにより、次の移動で都市の三つ組の条件に反しないかが判定できる。

都市の三つ組は単純にsetなどに入れておけばいい。

ソースコード

struct edge{ int from,to,next; };
edge es[40002];
int e[3000],E;
int n,m,k;
void add_edge(int u,int v){
	es[E]=(edge){ u,v,e[u] };
	e[u]=E++;
	es[E]=(edge){ v,u,e[v] };
	e[v]=E++;
}
set<pair<pi,int> > bad;
int prev[40002];

void run()
{
	cin>>n>>m>>k;
	E=1;
	rep(i,m){
		int s,t; cin>>s>>t;
		add_edge(s-1,t-1);
	}
	rep(i,k){
		int a,b,c; cin>>a>>b>>c;
		bad.insert(mp(mp(a-1,b-1),c-1));
	}
	es[E]=(edge){ -1,0,0 };
	queue<int> q;
	q.push(E++);
	
	while(!q.empty()){
		int cure=q.front(); q.pop();
		int cur=es[cure].to, prv=es[cure].from;
		
		if(cur==n-1){
			vi ans;
			for(;cure;cure=prev[cure])ans.pb(es[cure].to);
			cout<<ans.size()-1<<endl;
			reverse(all(ans));
			rep(i,ans.size())cout<<ans[i]+1<<(i==ans.size()-1?"\n":" ");
			return;
		}
		for(int p=e[cur];p;p=es[p].next){
			if(bad.count(mp(mp(prv,cur),es[p].to))||prev[p]!=0)continue;
			prev[p]=cure;
			q.push(p);
		}
	}
	cout<<-1<<endl;
}