URAL 1980. Road to Investor

Author: 2015-08-27

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1980

1980. Road to Investor

Time limit: 1.0 second
Memory limit: 64 MB
‘How could I forget it? In T hours we must show the alpha-version of our game to a potential investor! This meeting is crucial for us! If we miss it, we possibly won’t have a chance to complete the development.’
‘Don’t panic! Where do they wait for us?’
‘In their Tmutarakan office. Let’s go right now. I think we’ll be there in time, but we’ll have to exceed the speed limit in a couple of places.’
‘We don’t need problems with the police—we’ll lose precious time. We’ll work out a route to get to the investor in time such that the maximal needed overspeeding along this route is as minimal as possible.’

Input

The first line contains the number n of crossroads and the number m of roads between them (2 ≤ n ≤ 10 000;1 ≤ m ≤ 10 000). All the roads have two-way traffic. The i-th of the following m lines contains integers ai, bi, si, and li(1 ≤ ai < bi ≤ n; 1 ≤ si ≤ 300; 1 ≤ li ≤ 1 000), which mean that there is an li-kilometer long road with speed limit sikilometers per hour between crossroads ai and bi. The game developers’ office is at crossroad 1, and the investor’s office is at crossroad n. It is guaranteed that there is a way from crossroad 1 to crossroad n. The last line contains the number T of hours left before the meeting (1 ≤ T ≤ 106).

Output

Describe a route by which the developers can get to the investor’s office in time with minimum overspeeding. In the first line output numbers S and k, which are the minimum overspeeding in kilometers per hour and the number of roads in the route. In the second line output k integers separated with a space. The integers are the numbers of roads in the order in which they must be traveled. The roads are numbered from 1 to m in the order in which they are given in the input. If there are several ways to get to the investor’s office with the overspeeding S, output any of them. The absolute or relative error of Sshould not exceed 10−6.

Samples

input output 
3 3
1 3 50 150
1 2 80 100
2 3 80 100
2

20.000000 2
2 3

2 1
1 2 60 60
1

0.000000 1
1
Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013

2. 思路

有若干条路，给出路与路之间的连接关系，以及每条路的长度和限速，要在时间限制内从一点到另一点，时间不够，可以超速行驶，求能在时限内到达的最小超速速度。
需要理解清楚的是，所求的超速速度是以每条路的限速为基准的，如题目给出的第一组数据，超速速度为20.000000，三条路限速分别为50、80、80，则在这三条路上的实际行驶速度为70、100、100。
对超速速度进行二分搜索，对每一个超速速度，再搜索最快路径，判断是否满足时限要求。

3.代码

#include <stdio.h>
#include <math.h>
#include <queue>

using namespace std;

#define MAX_ROAD_NUM 10001
#define MAX_COST_TIME 0x1FFFFFFF
#define ERROR 0.0000001

typedef int CrossIdType;
typedef int SpeedType;

typedef struct RoadRecord {
	CrossIdType a, b;
	double s;
	double l;
	int id, next;
} Road;

void solveE5e_RoadToInvestor();
void inputRoads(Road roads[], int num);
double getMinTime(Road roads[], int roadNum, int destCrossId, double overspeed);

int main() {
	solveE5e_RoadToInvestor();
	return 0;
}

Road roads[MAX_ROAD_NUM];
double costTime[MAX_ROAD_NUM];
int pre[MAX_ROAD_NUM], selectedRoadIdPre[MAX_ROAD_NUM], selectedRoadId[MAX_ROAD_NUM], index[MAX_ROAD_NUM];
queue<int> q;
bool visited[MAX_ROAD_NUM];
void solveE5e_RoadToInvestor() {
	int n, m, timeLimit;
	scanf("%d %d", &n, &m);
	inputRoads(roads, m);
	scanf("%d", &timeLimit);
	getMinTime(roads, m, n, 20);

	double l = 0, r = 100000000, mid = (l + r) / 2.0;
	while (fabs(r - l) > ERROR) {
		if (getMinTime(roads, m, n, mid) <= timeLimit) {
			r = mid;
		}
		else {
			l = mid;
		}
		mid = (l + r) / 2.0;
	}

	int cnt = 0;
	for (int i = n; pre[i] != 0; i = pre[i]) {
		selectedRoadId[cnt++] = selectedRoadIdPre[i];
	}
	printf("%.6lf %d\n", mid, cnt);

	for (int i = cnt - 1; i >= 0; --i) {
		printf("%d ", selectedRoadId[i]);
	}
	printf("\n");

}

void inputRoads(Road roads[], int num) {
	for (int i = 0; i <= num; ++i) {
		index[i] = -1;
	}

	for (int i = 0; i < num; ++i) {
		scanf("%d %d %lf %lf", &roads[i].a, &roads[i].b, &roads[i].s, &roads[i].l);
		roads[i].id = i+1;
		roads[i].next = index[roads[i].a];
		index[roads[i].a] = i;
	}
}

double getMinTime(Road roads[], int roadNum, int destCrossId, double overspeed) {
	costTime[1] = 0;
	q.push(1);
	visited[1] = true;
	for (int i = 2; i <= destCrossId; ++i) {
		visited[i] = false;
		costTime[i] = MAX_COST_TIME;
	}

	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		visited[curr] = false;
		for (int i = index[curr]; ~i; i = roads[i].next)
		{
			int next = roads[i].b;
			double w = roads[i].l / (roads[i].s + overspeed);
			if (costTime[next]>costTime[curr] + w)
			{
				costTime[next] = costTime[curr] + w;
				pre[next] = curr;
				selectedRoadIdPre[next] = roads[i].id;

				if (!visited[next])
				{
					visited[next] = true;
					q.push(next);
				}
			}
		}
	}
	return costTime[destCrossId];
}