记录编号	160168	评测结果	AAAATTTTTTTTAAA
题目名称	相遇时间	最终得分	46
用户昵称	wolf.	是否通过	未通过
代码语言	C++	运行时间	8.193 s
提交时间	2015-04-24 12:39:47	内存使用	0.11 MiB

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="	";
ofstream nnew("meeting.in",ios::app);
ifstream fin("meeting.in");
#define fout cout
#define Endl endl
#else
ifstream fin("meeting.in");
ofstream fout("meeting.out");
#endif
class llink{
public:
	int from,to;
	int C,D;
	llink(){
	}
	llink(int a,int b,int c,int d){
		from=a;
		to=b;
		C=c;
		D=d;
	}
};
vector<vector<int> > index;
vector<llink> TT;
vector<int> AA[105];
vector<int> BB[105];
void work1(int n){
	AA[1].push_back(0);
	vector<bool> flag;
	flag.resize(105,0);
	queue<int> Q;
	Q.push(1);
	while(!Q.empty()){
		int it=Q.front();
		Q.pop();
		flag[it]=0;
		for(int i=0;i!=index[it].size();++i){
			llink& pp=TT[index[it][i]];
			vector<bool> ttime;
			ttime.resize(10000,0);
			for(int j=0;j!=AA[it].size();++j){
				if(ttime[AA[it][j]]){
					continue;
				}
				ttime[AA[it][j]]=1;
				AA[pp.to].push_back(AA[it][j]+pp.C);
			}
			if(flag[pp.to]==0){
				flag[pp.to]=1;
				Q.push(pp.to);
			}
		}
	}
	sort(AA[n].begin(),AA[n].end());
}
void work2(int n){
	BB[1].push_back(0);
	vector<bool> flag;
	flag.resize(105,0);
	queue<int> Q;
	Q.push(1);
	while(!Q.empty()){
		int it=Q.front();
		Q.pop();
		flag[it]=0;
		for(int i=0;i!=index[it].size();++i){
			llink& pp=TT[index[it][i]];
			vector<bool> ttime;
			ttime.resize(10000,0);
			for(int j=0;j!=BB[it].size();++j){
				if(ttime[BB[it][j]]){
					continue;
				}
				ttime[BB[it][j]]=1;
				BB[pp.to].push_back(BB[it][j]+pp.D);
			}
			if(flag[pp.to]==0){
				flag[pp.to]=1;
				Q.push(pp.to);
			}
		}
	}
	sort(BB[n].begin(),BB[n].end());
}
int core(int n){
	work1(n);
	work2(n);
	int a=0,b=0;
	while(a<AA[n].size()&&b<BB[n].size()){
		if(AA[n][a]==BB[n][b]){
			return AA[n][a];
		}
		if(AA[n][a]<BB[n][b]){
			++a;
		}
		if(AA[n][a]>BB[n][b]){
			++b;
		}
	}
	return -1;
}
int main(){
	int n,m;
	fin>>n>>m;
	index.resize(n+5);
	for(int i=0;i!=m;++i){
		int a,b,c,d;
		fin>>a>>b>>c>>d;
		index[a].push_back(TT.size());
		TT.push_back(llink(a,b,c,d));
	}
	int r=core(n);
	if(r==-1){
		fout<<"IMPOSSIBLE"<<endl;
	}else{
		fout<<r<<endl;
	}
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Fri Apr 24 2015