记录编号	200099	评测结果	AAAAAAAAAAAAAAA
题目名称	相遇时间	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.667 s
提交时间	2015-10-27 21:41:40	内存使用	2.24 MiB

#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define N 101
#define M 10010
using namespace std;
ifstream in("meeting.in");
ofstream out("meeting.out");
int n,m,T=0;
vector<int> G[N],C[N],D[N];
bool l[N]={0};
bool f[N][M]={0},g[N][M]={0};
void read()
{
	int i,a,b,c,d;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>a>>b>>c>>d;
		G[a].push_back(b);
		C[a].push_back(c);
		D[a].push_back(d);
		T+=c;T+=d;
	}
	T=min(T,M-10);
	//out<<T<<endl;
}
void work()
{
	int i,j,k,u,v,wx,wy;
	f[1][0]=1;
	g[1][0]=1;
	for(i=1;i<=n;i++)
	{
		u=i;
		for(j=0;j<G[i].size();j++)
		{
			v=G[i][j];wx=C[i][j];wy=D[i][j];
			for(k=min(wx,wy);k<=T;k++)
			{
				if(k>=wx)
				{
					if(f[u][k-wx])f[v][k]=1;
				}
				if(k>=wy)
				{
					if(g[u][k-wy])g[v][k]=1;
				}
			}
		}
	}
	bool flag=0;
	for(i=0;i<=T;i++)
	{
		if(f[n][i]&&g[n][i])
		{
			out<<i<<endl;
			flag=1;
			break;
		}
	}
	if(!flag)out<<"IMPOSSIBLE"<<endl;
}
int main()
{
	read();
	work();
	return 0;
}