AtCoder ABC #143 : E - Travel by Car

SRMで凹んだ後の参加。
https://atcoder.jp/contests/abc143/tasks/abc143_e

問題

N個の町と、町をつなぐM個の道がある。
道にはそれぞれ長さが設定されている。

以下のクエリに順次答えよ。

• 燃料タンクの容量Lを使い、町S→Tに移動する。その際、道を通ると距離1あたり燃料を1消費する。
  • 初期状態でタンクは満タンであり、各町で再度満タンにできる場合、Tに移動する最小補充回数を求めよ。

解法

まず、1回のタンクでどこからどこまで行けるかを考える。
これはWarshall-Floydで全町間の最短路を求めて、Lがそれ以下か判定すればよい。

次に、町から町にタンク何杯分かかるかを考えるが、これは先ほどの判定で距離L内の町は1杯で行ける、と考えて再度Warshall-Floyedを回せばよい。

int N,M,L;
vector<pair<int,int>> E[303];

ll dp[303][303];
int cost[303][303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>M>>L;
	FOR(x,N) FOR(y,N) dp[x][y]=(x==y?0:1LL<<60);
	FOR(i,M) {
		cin>>x>>y>>r;
		dp[x-1][y-1]=dp[y-1][x-1]=r;
	}
	
	FOR(r,N) FOR(x,N) FOR(y,N) dp[x][y]=min(dp[x][y],dp[x][r]+dp[r][y]);
	FOR(x,N) FOR(y,N) cost[x][y]=(x==y)?0:(dp[x][y]<=L?1:(1LL<<20));
	FOR(r,N) FOR(x,N) FOR(y,N) cost[x][y]=min(cost[x][y],cost[x][r]+cost[r][y]);
	
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		x--,y--;
		if(cost[x][y]>=1000) cout<<-1<<endl;
		else cout<<cost[x][y]-1<<endl;
		
	}
	
	
}

まとめ

無駄にDijkstra回してTLEしちゃった。