Codeforces #214 Div2. D. Dima and Trap Graph

最初題意を誤解したけど、題意を正しく理解したらすんなり解けた。
http://codeforces.com/contest/366/problem/D

問題

N点・M辺からなる無向グラフが与えられる。
各辺にはパラメータL[i]・R[i]が与えられる。

このグラフにおいて、先頭の点から末尾の点に移動したい。
この時、開始時にパラメータxを一つ選択し、グラフをたどるがL[i]<=x<=R[i]を満たす辺しかたどることができない。

先頭から末尾の点に移動可能なパスのうち、選択できるxの範囲が最も広いものを答えよ。

解法

最初問題を勘違いして、「末尾の点に移動できるxを求めよ」だと思った。
それでコードを書いた後、「xの範囲が広い"単一の"パスを求めよ」だということに気が付いた。

辺をR[i]の値で降順ソートし、１本ずつ辺を加えていく。
この時、R[0]～R[i-1]はR[i]以上なので、x<=R[i]ならすべての辺を通ることができる。
あとは先頭の点から末尾の点まで到達できる最小のxをdijkstraで求めれば、(R[i]-x+1)が選択できるxの数。

辺を足しながら(R[i]-x+1)を最大化すればよい。
辺の数が3000本程度なので、dijkstraを3000回やっても1～2秒で終わる。

int N,M;
pair<int, pair<int,int> > D[4001];
map<int,int> mat[1001];

int dpdp() {
	int mx[1001];
	int i,x;
	FOR(i,N) mx[i]=1<<29;
	mx[0]=0;
	
	set<pair<int,int> > S;
	S.insert(make_pair(0,0));
	while(!S.empty()) {
		pair<int,int> p=*S.begin();
		S.erase(p);
		if(p.first>mx[p.second]) continue;
		ITR(it,mat[p.second]) {
			x=max(p.first,it->second);
			if(x<mx[it->first]) {
				mx[it->first]=x;
				S.insert(make_pair(x,it->first));
			}
		}
	}
	return mx[N-1];
}

void solve() {
	int f,i,j,k,l,x,y,r;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>l>>r;
		x--;
		y--;
		D[i].first=r;
		D[i].second.first=l;
		D[i].second.second=x*10000+y;
	}
	
	sort(D,D+M);
	int res=0;
	for(i=M-1;i>=0;i--) {
		x=D[i].second.second/10000;
		y=D[i].second.second%10000;
		if(mat[x].find(y)==mat[x].end() || mat[x][y]>D[i].second.first)
			mat[x][y]=mat[y][x]=D[i].second.first;
		res=max(res,D[i].first-dpdp()+1);
	}
	
	if(res) return _P("%d\n",res);
	_P("Nice work, Dima!\n");
}

まとめ

今回問題文の誤読がひどいわ。
まぁその後はちゃんと解ききれてよかった。