记录编号	358942	评测结果	AAAAAAAAAAAAAAA
题目名称	相遇时间	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.181 s
提交时间	2016-12-19 21:04:56	内存使用	2.15 MiB

#include<cstdio>
#include<vector>
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int qr(){
		int x=0,ch=gc();
		while(ch<'0'||ch>'9'){ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
		return x;}
}using namespace IO;
using namespace std;
/***********************************************************************************************/
struct edge{
	int to;
	int w;}e1,e2;
int max1(int x,int y){
	return x>y? x:y;}
vector <edge> s1[200];
vector <edge> s2[200];
int main(){
	freopen ("meeting.in","r",stdin);
	freopen ("meeting.out","w",stdout);
	bool f1[101][10010]={0},f2[101][10010]={0};
	int i,N,M,a,b,c,d,T,maxw=0,j,k;
	N=qr();M=qr();
	for(i=1;i<=M;i++){
		a=qr();b=qr();c=qr();d=qr();
		maxw=max1(maxw,c);
		maxw=max1(maxw,d);
		e1.to=b;e2.to=b;
		e1.w=c;e2.w=d;
		s1[a].push_back(e1);
		s2[a].push_back(e2);}
	T=maxw*N;
	f1[1][0]=true;
	f2[1][0]=true;
	for(i=1;i<=N;i++){
		for(j=0;j<=T;j++){
			if(!f1[i][j]){
				continue;}
			for(k=0;k<(int)s1[i].size();k++){
				int t=s1[i][k].to;
				int w=s1[i][k].w;
				f1[t][j+w]=true;}}}
	for(i=1;i<=N;i++){
		for(j=0;j<=T;j++){
			if(!f2[i][j]){
				continue;}
			for(k=0;k<(int)s2[i].size();k++){
				int t=s2[i][k].to;
				int w=s2[i][k].w;
				f2[t][j+w]=true;}}}
	for(i=0;i<=T;i++){
		if(f1[N][i]&&f2[N][i]){
			printf("%d",i);
			return 0;}}
	printf("IMPOSSIBLE");
	return 0;
}
/*int chh=sb();
int main(){
	return 0;
}*/