CSAcademy Round #54 : E. Late Edges

最初変な解法を取ってTLEした。
https://csacademy.com/contest/round-54/task/late-edges/

問題

N頂点の無向グラフがある。
プライヤーは最初1番の頂点にいて、1秒毎に辺で結ばれたいずれかの頂点に移動しなければならない。
なお、各辺はある時間から移動可能になり、それぞれ異なる時間が与えられる。

最適に移動するとき、N番の頂点に移動する最短時間を求めよ。

なお、初期状態で1番の点に移動可能な辺が1本以上あることは保障される。

解法

ある頂点に移動すると、そこから移動可能な辺が最低1本はあるので、そこを移動すると2ずつ時間を増やしていくことが可能である。
よって、各頂点偶数・奇数時間で最初に到達する時間をそれぞれ持ち、ダイクストラ法を実行すればよい。

int N,M;
vector<pair<int,int>> E[5050];
int D[5050][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	FOR(i,N) D[i][0]=D[i][1]=1<<30;
	D[0][0]=0;
	priority_queue<pair<int,int>> Q;
	Q.push({0,0});
	while(Q.size()) {
		int co=-Q.top().first;
		int cur=Q.top().second/2;
		int odd=Q.top().second%2;
		Q.pop();
		if(D[cur][odd]!=co) continue;
		
		FORR(e,E[cur]) {
			int tim=max(co,e.second+((co%2)!=(e.second%2)));
			if(D[e.first][odd^1] > tim+1) {
				D[e.first][odd^1]=tim+1;
				Q.push({-D[e.first][odd^1],e.first*2+(odd^1)});
			}
		}
		
	}
	
	
	int ret=min(D[N-1][0],D[N-1][1]);
	if(ret>=1<<30) ret=-1;
	cout<<ret<<endl;
}

まとめ

どこかでこんなん見たなぁ…。