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

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define USEFREAD
#ifdef USEFREAD
#define InputLen 5000000
char *ptr=(char *)malloc(InputLen);
#define getc() (*(ptr++))
#else
#define getc() (getchar())
#endif
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
	int ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))
		x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 102, maxd = 10002;
bool tag1[maxn][maxd], tag2[maxn][maxd];
int N, M, adj_d[maxn], MAX;
struct Edge{int to, C, D;}adj[maxn][maxn];

inline void init(){
	getd(N), getd(M);
	MAX = 0;
	int a, b, c, d, i, j, k, t;
	while(M--){
		getd(a), getd(b), getd(c), getd(d);
		MAX = max(MAX, max(c, d));
		adj[a][adj_d[a]++] = (Edge){b, c, d};
	}
	*tag1[1] = *tag2[1] = true;
	MAX *= N;
	for(i = 1;i < N;++i)for(j = 0;j < adj_d[i];++j){
		c = adj[i][j].C;
		t = adj[i][j].to;
		for(k = 0;k + c <= MAX;++k)if(tag1[i][k])
			tag1[t][k+c] = true;
	}
	for(i = 1;i < N;++i)for(j = 0;j < adj_d[i];++j){
		d = adj[i][j].D;
		t = adj[i][j].to;
		for(k = 0;k + d <= MAX;++k)if(tag2[i][k])
			tag2[t][k+d] = true;
	}
	
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else       
	SetFile(meeting);
	#endif
	#ifdef USEFREAD
	fread(ptr,1,InputLen,stdin);
	#endif
	
	init();
	
	for(int i = 0;i <= MAX;++i)if(tag1[N][i] && tag2[N][i]){
		printf("%d\n", i);
		return 0;
	}
	puts("IMPOSSIBLE");
	
#ifdef DEBUG
    printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}