Flights

#include <iostream>
#include <vector>
#include <queue>

#define ll long long
#define mp make_pair
#define F first
#define S second
#define INF 999999999999999
#define ld long double

using namespace std;


pair<pair<ll,ll>,pair<int,int>> e[201010];
vector<int> v1[101010], v2[101010];
int n,m;
priority_queue<pair<ll,int>> pq;

int t[101010],t2[101010];
ll dist[101010], dist2[101010];

void dijkstra() {
	for (int i=1;i<=n;i++) dist[i]=INF;
	dist[1]=0;
	pq.push(mp(0,1));
	while (!pq.empty()) {
		ll x = -pq.top().first;
		int s = pq.top().second;
		pq.pop();
		if (t[s]) continue;
		t[s] = 1;
		for (unsigned int i = 0; i < v1[s].size(); i++) {
			int u = e[v1[s][i]].S.S;
			if (x+e[v1[s][i]].F.F < dist[u]) {
				dist[u] = x+e[v1[s][i]].F.F;
				pq.push(make_pair(-dist[u],u));
			}
		}
	}
}

void dijkstra2() {
        for (int i=1;i<=n;i++) dist2[i]=INF;
        dist2[n]=0;
        pq.push(mp(0,n));
        while (!pq.empty()) {
                ll x = -pq.top().first;
                int s = pq.top().second;
                pq.pop();
                if (t2[s]) continue;
                t2[s] = 1;
                for (unsigned int i = 0; i < v2[s].size(); i++) {
                        int u = e[v2[s][i]].S.F;
                        if (x+e[v2[s][i]].F.F < dist2[u]) {
                                dist2[u] = x+e[v2[s][i]].F.F;
                                pq.push(make_pair(-dist2[u],u));
                        }
                }
        }
}



int main() {
	cin >> n >> m;
	for (int i=0;i<m;i++) {
		int a,b;
		ll p,x;
		cin >> a >> b >> p >> x;
		v1[a].push_back(i);
		v2[b].push_back(i);
		e[i]=mp(mp(p,x),mp(a,b));
	}
	dijkstra();
	dijkstra2();
//	for (int i=1;i<=n;i++) cout << dist[i] << " " << dist2[i] << endl;
	ll parsa =4*99*INF;
	for (int i=0;i<m;i++) {
		ll res = dist[e[i].S.F];
		res += dist2[e[i].S.S];
		res+=e[i].F.F;
		res*=e[i].F.S;
		if (res < parsa) parsa = res;
	}
	cout << parsa/100;
	if (parsa%100) cout << "." << (parsa/10)%10 << parsa%10;
	cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

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