Flights

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <stack>
#include <iomanip>
 
using namespace std;
 
#define all(x) (x).begin(),x.end()
#define ii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
 
#define MAXN 100001
const ll INF = (ll)1e17;
 
int n, m;
vector<int> eList[MAXN], erList[MAXN];
vector<ll> cList[MAXN], crList[MAXN], dList[MAXN];
 
void dijkstra(int start, vector<int> *eList, vector<ll> *cList, vector<ll> &d) {
	priority_queue<ii, vector<ii>, greater<ii> > q;
	d[start] = 0;
	q.push(ii(0, start));
 
	while (!q.empty()) {
		ii top = q.top();
		q.pop();
 
		int i = top.se;
		if (top.fi > d[i]) {
			continue;
		}
 
		for (int k = 0; k < (int)eList[i].size(); k++) {
			int j = eList[i][k];
			int c = cList[i][k];
			if (d[j] > d[i] + c) {
				d[j] = d[i] + c;
				q.push(ii(d[j], j));
			}
		}
	}
}
 
int main() {
	cin >> n >> m;
 
	int u, v;
	ll p, x;
 
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> p >> x;
		u--; v--;
 
		eList[u].pb(v);
		cList[u].pb(p);
		dList[u].pb(x);
 
		erList[v].pb(u);
		crList[v].pb(p);
	}
 
	vector<ll> d(n, INF);
	dijkstra(0, eList, cList, d);
 
	vector<ll> dr(n, INF);
	dijkstra(n-1, erList, crList, dr);
 
	// for (int i = 0; i < n; i++) {
	// 	cout << d[i] << " ";
	// }
	// cout << endl;
	// for (int i = 0; i < n; i++) {
	// 	cout << dr[i] << " ";
	// }
 
	double res = (double) INF;
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < (int) eList[i].size(); k++) {
			int j = eList[i][k];
			double cost = d[i] + cList[i][k] + dr[j];
			double mul = dList[i][k]*0.01;
			res = min(res, cost*mul);
			// }
		}
	}
 
	cout << setprecision(17) << res << endl;
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED