JAG夏合宿Day4 F Marching Course

問題

F: Marching Course - Japan Alumni Group Summer Camp 2015 Day 4 | AtCoder

問題概要

無向連結グラフが与えられる。各辺には距離(d)と客(v)をもつ。
このグラフをマーチングバンドが頂点1から単位時間あたり距離1で練り歩き、
時間P以内に再び頂点1に戻ってくることを考える。
このとき、ある辺上にいた時間をmとするとの注目度が得られるので、これを最大化したい。
また、マーチングバンドは辺上にいるとき任意のタイミングで反対方向を向き引き返すこともできる。

解法

のときでも解く事が可能だそうですが、ここではとして

まず、辺の上で引き返すことができないとした場合、dp[頂点][経過時間]としてdpを更新するorダイクストラすれば注目度の最大値を求めることができる。

返上を引き返すことができるという条件を考える。

こんな感じに返上を移動するときは

こんな感じの移動に置き換えても支障がない

またこんな感じの移動はありえず、引き返すという動作は単位距離あたりの客の数が一番いい返上でひたすら行えばいい。

したがって、各頂点について、辺の中で単位距離あたりの客の数が一番いい辺を距離1の自己辺として張りなおせば返上を引き返すということを表現できる。

ソース

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF 100000000
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long

using namespace std;

typedef pair<int, double> ID;
typedef pair<int, ID> IID;

#define MAX_N 201
#define MAX_P 1001

int N, M, P;
vector<IID> Edge[MAX_N];

void makeEdge(){

	for (int i = 0; i < N; i++){
		
		double v_max = 0;

		for (int j = 0; j < Edge[i].size(); j++){
			IID e = Edge[i][j];
			v_max = max(v_max, e.second.second / e.second.first);
		}

		Edge[i].push_back(IID(i, ID(1, v_max)));

	}

}

double dp[MAX_N][MAX_P];

int main(){

	cin >> N >> M >> P;
	for (int i = 0; i < M; i++){
		int s, t, d, v;
		cin >> s >> t >> d >> v;
		s--;
		t--;
		Edge[s].push_back(IID(t, ID(d, v)));
		Edge[t].push_back(IID(s, ID(d, v)));
	}

	makeEdge();

	for (int i = 0; i < N; i++){
		for (int j = 0; j <= P; j++){
			dp[i][j] = -1;
		}
	}

	dp[0][0] = 0;

	for (int p = 0; p < P; p++){
		for (int pos = 0; pos < N; pos++){
			if (dp[pos][p] < 0.0)
				continue;
			for (int i = 0; i < Edge[pos].size(); i++){
				IID edge = Edge[pos][i];
				int nextPos = edge.first;
				int nextTime = p + edge.second.first;
				double nextPoint = dp[pos][p] + edge.second.second;
				if (nextTime <= P){
					dp[nextPos][nextTime] = max(dp[nextPos][nextTime], nextPoint);
				}
			}
		}
	}

	printf("%.10f\n", dp[0][P]);

	return 0;

}