记录编号	160174	评测结果	AAAAAAAAAAAAAAA
题目名称	相遇时间	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.567 s
提交时间	2015-04-24 14:04:46	内存使用	2.32 MiB

#include<fstream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 101
#define BESSIE 0
#define ELSIE 1
#define MAXW 10001
using namespace std;
ifstream fin("meeting.in");
ofstream fout("meeting.out");
int N,M;
queue<int>q[MAXN];
queue<int>Q;
int W[MAXN][MAXN][2],to[MAXN];
bool F[MAXN][MAXW],G[MAXN][MAXW];
int main()
{
	fin>>N>>M;
	int u,v,w1,w2;
	memset(F,0,sizeof(F));
	memset(G,0,sizeof(G));
	memset(to,0,sizeof(to));
	for(int i=1;i<=M;i++)
	{
		fin>>u>>v>>w1>>w2;
		q[u].push(v);
		W[u][v][BESSIE]=w1;
		W[u][v][ELSIE]=w2;
		to[v]++;
	}
	F[1][0]=G[1][0]=1;
	for(int i=1;i<=N;i++) if(!to[i]) Q.push(i);
	while(!Q.empty())
	{
		u=Q.front();Q.pop();
		while(!q[u].empty())
		{
			v=q[u].front();q[u].pop();
			for(int j=0;j+W[u][v][BESSIE]<MAXW;j++) F[v][j+W[u][v][BESSIE]]|=F[u][j];
			for(int j=0;j+W[u][v][ELSIE]<MAXW;j++) G[v][j+W[u][v][ELSIE]]|=G[u][j];
			to[v]--;
			if(!to[v]) Q.push(v);
		}
	}
	for(int i=0;i<MAXW;i++)
	{
		if(F[N][i]&G[N][i])
		{
			fout<<i<<endl;
			return 0;
		}
	}
	fout<<"IMPOSSIBLE"<<endl;
	return 0;
}