SRM 652 Div1 Medium MaliciousPath

K = 0 のときは、 dijkstra で解ける。
頂点を *1 と拡張すると、K>0 の場合も dijkstra を多少書き換えるだけで解くことができる。
辺の長さが少し特殊なので、k=0..K として順番に dijkstra を行うことで効率よく最短路が求まる。
計算量は、O(K(N+M)logN)となる。

下記コードは editorial や他人の解説記事を読んだ感じではおそらく正しいが、practice ルームでは TLE となるので注意。(同じような現象が最近 (2018/02/07) よく起こるので、サーバ側の問題だと思う)

#define NN 1010
vector<P> g[NN], g2[NN];
ll d[NN][NN], d2[NN][NN];

class MaliciousPath {
	public:
	long long minPath(int n, int K, vector <int> f, vector <int> t, vector <int> c) {
		rep(i, n) g[i].clear();
		rep(i, n) g2[i].clear();
		int m = f.size();
		rep(i, m){
			g[f[i]].pb(P(c[i], t[i]));
			g2[t[i]].pb(P(c[i], f[i]));
		}
		rep(i, n){
			sort(all(g[i]));
			sort(all(g2[i]));
		}
		rep(i, n) fill(d[i], d[i]+NN, INF);
		mset(d2, 0);
		rep(k, K+1) d[n-1][k] = 0;
		rep(k, K+1){
			priority_queue<P, vector<P>, greater<P>> q;
			q.push(P(0, n-1));
			while(!q.empty()){
				P p = q.top(); q.pop();
				ll l = p.fst, u = p.snd;
				if(d[u][k]<l) continue;
				for(auto x: g2[u]){
					ll l2 = max(d2[x.snd][k], l+x.fst), v = x.snd;
					if(d[v][k]>l2){
						d[v][k] = l2;
						q.push(P(l2, v));
					}
				}
			}
			rep(i, m) chmax(d2[f[i]][k+1], d[t[i]][k]+c[i]);
		}
		return d[0][K]==INF?-1:d[0][K];
	}
};

*1:頂点), (token数