Flights

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

#define ll long long
#define ld long double
#define ii pair<int,int>
#define si pair<string,int>
#define iii pair<int,ii>
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define msvs map<string,vs>
#define msi map<string,int>
#define mss map<string,int>
#define us unordered_set
#define um unordered_map
#define pq priority_queue
#define pb push_back
#define mp make_pair
#define forall(i,a,b) for (int i=a;i<b;i++)
#define foreach(v,c) for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a) a.begin(), a.end()
#define in(a,b) ( (b).find(a) != (b).end())
#define fill(a,v) memset(a, v, sizeof a)
#define sz(a) ((int)(a.size()))
#define N (1<<17)
#define M 1000000007


int n,m;


int main()
{
	map<int, vector<pair<int,pair<int,int>>>> edges;
	map<int,pair<ll,int>> prices;
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a,b,p,d;
		cin >> a >> b >> p >> d;
		edges[a].push_back(make_pair(b,make_pair(p,d)));
	}
	deque<pair<int,pair<ll,int>>> q;
	q.push_back(make_pair(1,make_pair((ll)0,100)));
	while (!q.empty()) {
		pair<int,pair<ll,int>> current = q.front();
		q.pop_front();
		vector<pair<int,pair<int,int>>> kaaret = edges[current.first];
		for (pair<int,pair<int,int>> cinfo : kaaret) {
			ll total = current.second.first + cinfo.second.first;
			int discount = min(current.second.second,cinfo.second.second);
			if (prices.find(cinfo.first) != prices.end()) {
				long double tot = (discount / (long double)100) * total;
				long double oldtot = (prices[cinfo.first].second / (long double)100) * prices[cinfo.first].first;
				if (tot < oldtot) {
					prices[cinfo.first] = make_pair(total,discount);
					q.push_back(make_pair(cinfo.first,make_pair(total,discount)));
				}
			} else {
				prices[cinfo.first] = make_pair(total,discount);
				q.push_back(make_pair(cinfo.first,make_pair(total,discount)));
			}
		}
	}
	cout << (prices[n].second / (long double)100) * prices[n].first;
	return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: TIME LIMIT EXCEEDED

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: TIME LIMIT EXCEEDED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: TIME LIMIT EXCEEDED

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: TIME LIMIT EXCEEDED

Test 28

Verdict: TIME LIMIT EXCEEDED

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER