Description：

给两排点，包括这两排点的一个 $DAG$ ，两排点之间还有一些边，从 $n$ 号点出发，走到 $k$ 点的代价是通行时间和比上安全系数和，走到一个点就可以控制所有和这个点相邻的两排点之间的边，要控制所有两排点之间的边，最小化总代价。

$1\leqslant n\leqslant 700,1\leqslant m\leqslant 100000,$ 两排点数 $\leqslant 161$

Solution：

首先假设我们求出了从 $n$ 到每个点的距离，那这就是一个二分图最小权点覆盖，那么新建源点和汇点，分别连边代表这个点的点权，二分图之间的边连 $\infty$ ，那么最小割就是答案，于是现在我们的问题就变成了如何求出从 $n$ 到每个点的距离，发现这个距离是一个 $01$ 分数规划的模型，那么可以二分，由于是 $DAG$ 所以可以拓扑求最短路。

时间复杂度 $O($ 两排点数 $\times\log$ 值域 $\times(n+m)+dinic)$ 。

可以整体二分，但是好像并不会特别优秀，因为点数非常少。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

namespace G//Graph

{

	int n,m;

	const int MAXN = 710;

	const int MAXM = 100000;

	struct edges

	{

		int fr,to,v1,v2;

	}es[MAXM];

	int ecnt = 0;

	void addedge(int a,int b,int v1,int v2)

	{

		es[++ecnt] = (edges){a,b,v1,v2};

		return;

	}

	struct edge

	{

		int to,nxt;

		double v;

	}e[MAXM];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,double v)

	{//cout << a << " -> " << b << " " << v << endl;

		e[++edgenum] = (edge){b,lin[a],v};lin[a] = edgenum;

		return;

	}

	double d[MAXN];

	int ind[MAXN];

	double calc(double v,int des)

	{

		memset(lin,0,sizeof(lin));

		memset(ind,0,sizeof(ind));

		for(int i = 1;i <= n;++i)d[i] = 1000000000;

		d[n] = 0.0;

		edgenum = 0;

		for(int i = 1;i <= m;++i)

		{

			++ind[es[i].to];

			add(es[i].fr,es[i].to,es[i].v1 - v * es[i].v2);

		}

		queue<int> q;

		for(int i = 1;i <= n;++i)if(ind[i] == 0)q.push(i);

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				d[e[i].to] = min(d[e[i].to],d[k] + e[i].v);

				if((--ind[e[i].to]) == 0)q.push(e[i].to);

			}

		}

		//for(int i = 1;i <= n;++i)cout << d[i] << " ";cout << endl;

		return d[des];

	}

}

namespace F//Flow

{

	int n,m;

	const int MAXN = 170;

	const int MAXM = 40010;

	double dis[MAXN];

	struct edge

	{

		int to,nxt;

		double f;

	}e[(MAXM + MAXN) * 2];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,double f)

	{

		e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

		e[edgenum] = (edge){a,lin[b],f};lin[b] = edgenum++;

		return;

	}

	int ch[MAXN];

	int s,t;

	bool BFS()

	{

		queue<int> q;q.push(s);

		memset(ch,-1,sizeof(ch));ch[s] = 0;

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = lin[k];i != -1;i = e[i].nxt)

			{

				if(ch[e[i].to] == -1 && e[i].f > 1e-4)

				{

					ch[e[i].to] = ch[k] + 1;

					q.push(e[i].to);

				}

			}

		}

		return ch[t] != -1;

	}

	double flow(int k,double f)

	{

		if(k == t)return f;

		double r = 0;

		for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

		{

			if(ch[e[i].to] == ch[k] + 1 && e[i].f > 1e-4)

			{

				double l = flow(e[i].to,min(e[i].f,f - r));

				e[i].f -= l;r += l;e[i ^ 1].f += l;

			}

		}

		if(r == 0)ch[k] = -1;

		return r;

	}

	double dinic()

	{

		double ans = 0,r;

		while(BFS())while((r = flow(s,10000000)) > 1e-4)ans += r;

		if(ans > 1000)return -1;

		return ans;

	}

}

int main()

{

	scanf("%d%d",&G::n,&G::m);

	int a,b,v1,v2;

	for(int i = 1;i <= G::m;++i)

	{

		scanf("%d%d%d%d",&a,&b,&v1,&v2);

		G::addedge(a,b,v1,v2);

	}

	scanf("%d%d",&F::m,&F::n);

	F::s = F::n + 1;F::t = F::n + 2;

	memset(F::lin,-1,sizeof(F::lin));

	for(int i = 1;i <= F::n;++i)

	{

		double l = 0,r = 100,mid;

		while(r - l > 1e-5)

		{

			mid = ((l + r) / 2);

			if(G::calc(mid,i) <= 0)r = mid;

			else l = mid;

		}

		F::dis[i] = l;

		if(i & 1)F::add(F::s,i,l);

		else F::add(i,F::t,l);

	}

	for(int i = 1;i <= F::m;++i)

	{

		scanf("%d%d",&a,&b);

		if(a & 1)F::add(a,b,100000000);

		else F::add(b,a,100000000);

	}

	double ans = F::dinic();

	if(ans != -1)printf("%.1lf\n",ans);

	else puts("-1");

	return 0;

}