记录编号	160146	评测结果	AAAAAAAAAAAAAAA
题目名称	相遇时间	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.188 s
提交时间	2015-04-24 12:05:23	内存使用	2.42 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=110,SIZET=10010;
int N,M,T;
void DP(vector<pair<int,int> > c[SIZEN],bool f[SIZEN][SIZET]){
	memset(f,0,sizeof(f));
	f[1][0]=true;
	for(int i=1;i<=N;i++){
		for(int j=0;j<=T;j++){
			if(!f[i][j]) continue;
			for(int k=0;k<c[i].size();k++){
				int u=c[i][k].first,w=c[i][k].second;
				if(j+w<=T){
					f[u][j+w]=true;
				}
			}
		}
	}
}
vector<pair<int,int> > BC[SIZEN],EC[SIZEN];
bool FB[SIZEN][SIZET],FE[SIZEN][SIZET];
void work(void){
	DP(BC,FB);
	DP(EC,FE);
	for(int i=0;i<=T;i++){
		if(FB[N][i]&&FE[N][i]){
			printf("%d\n",i);
			return;
		}
	}
	printf("IMPOSSIBLE\n");
}
void read(void){
	scanf("%d%d",&N,&M);
	int mx=0;
	int a,b,c,d;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if(a>b) swap(a,b);
		mx=max(mx,c);
		mx=max(mx,d);
		BC[a].push_back(make_pair(b,c));
		EC[a].push_back(make_pair(b,d));
	}
	T=N*mx;
}
int main(){
	freopen("meeting.in","r",stdin);
	freopen("meeting.out","w",stdout);
	read();
	work();
	return 0;
}