2014-06-13

SRM 624 Div1 450 DrivingPlans

01:31 |

閉路なし重複辺なしで連結なN頂点無向グラフと各辺上を移動するのにかかる時間が与えられる。頂点1→Nまでを最短時間でいくルートが何通りあるか mod 10^9+9 で求めよ。同じ頂点を複数回訪れてもいい。無限なら -1 を返す。
N≦2000, 0≦時間≦100000

(sampleにある通り,) 最短経路上にある点から時間 0 でいける点があれば行ったり来たりできるので無限通りになる所がポイントか。
組み合わせはなんとなく1→ある頂点に行く組み合わせ数を持っておいて足していくのだろう
とりあえずdijkstraで1→(少なくともNを開くまでの)全頂点の最短時間を求めておく
頂点1では1通りとして、1からの所要時間が短い順に頂点を見ていって、そこから出る辺が最短経路に含まれていたら組み合わせ数を足していく感じ
そこから時間0で行ける辺があったら-1を返す

modとってなかった
challenge される

(あとで)

というかそもそも間違っていた

SRM 622 Div1 250 BuildingRoutes と似てて、ある辺(u,v)がS→Eの最短経路集合に含まれるとは
cost(S→u)+cost(u→v)+cost(v→E) = cost(S→E)
cost(v→E) は S 始点の dijkstra では求まらないけど、この問題の場合無向グラフなので cost(v→E) = cost(E→v)
なので E 始点の dijkstra もしておけば O(1) で判定できる
最短経路上にある頂点それぞれについて、時間 0 で行ける辺があるなら return -1
すっきり

accepted in practice room

// たまにはマクロも
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define ALL(c) (c).begin(), (c).end()
#define MP(a, b) make_pair(a, b)
// Dijkstra略
class DrivingPlans {
	public:
	int count(int N, vector <int> A, vector <int> B, vector <int> C) {
		int M = A.size();
		Dijkstra d(N), r(N);
		REP(i, M) {
			d.add_edge(A[i]-1, B[i]-1, C[i]);
			d.add_edge(B[i]-1, A[i]-1, C[i]);
		}
		r=d;
		int co = d.run(0, N-1);
		r.run(N-1, 0);
		
		vector<PII> p(N);
		REP(i, N) p[i]=MP(d.V[i], i);
		sort(ALL(p));
		VI ways(N);
		ways[0] = 1;
		REP(i, N) {
			int from = p[i].second;
			REP(j, d.G[from].size()) {
				int to=d.G[from][j].to;
				if(d.V[from] + d.G[from][j].cost + r.V[to] == co) {
					ways[to] += ways[from];
					ways[to] %= 1000000009;
					REP(k, d.G[from].size()) if(d.G[from][k].cost==0) return -1;
					REP(k, d.G[to].size()) if(d.G[to][k].cost==0) return -1;
				}
			}
		}
		return ways[N-1];
	}
};

kojingharangの日記

2014-06-13

SRM 624 Div1 450 DrivingPlans