记录编号 358577 评测结果 AAAAAAAAAAAAAAA
题目名称 相遇时间 最终得分 100
用户昵称 GravatarShirry 是否通过 通过
代码语言 C++ 运行时间 0.191 s
提交时间 2016-12-17 00:15:56 内存使用 2.11 MiB
显示代码纯文本
#include<cstdio>//动态规划,从当前点出发,看能到达的距离
#include<vector>
#include<algorithm>
using namespace std;
struct poi{
	int v;
	int w;
};
vector<poi>E[2][101];
poi temp1,temp2;
int main(){
	freopen("meeting.in","r",stdin);
	freopen("meeting.out","w",stdout);
	int N,M;
	bool f[2][101][10000]={false};
	f[0][1][0]=true;
	f[1][1][0]=true;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++){
		int A,B,C,D;
		scanf("%d%d%d%d",&A,&B,&C,&D);
		temp1.v=B;
		temp1.w=C;
		temp2.v=B;
		temp2.w=D;
		E[0][A].push_back(temp1);
		E[1][A].push_back(temp2);
	}
	for(int i=1;i<=N;i++){
		for(int j=0;j<=10000;j++){
			if(!f[0][i][j])continue;
			else{
				for(int k=0;k<(int)E[0][i].size();k++){
					int u=E[0][i][k].v;
					int q=E[0][i][k].w;
					f[0][u][j+q]=true;
				}
			}
		}
	}
	for(int i=1;i<=N;i++){
		for(int j=0;j<=10000;j++){
			if(!f[1][i][j])continue;
			else{
				for(int k=0;k<(int)E[1][i].size();k++){
					int u=E[1][i][k].v;
					int q=E[1][i][k].w;
					f[1][u][j+q]=true;
				}
			}
		}
	}
	bool flag=false;
	for(int i=0;i<=10000;i++){
		if(f[0][N][i]==true&&f[1][N][i]==true){
			printf("%d",i);
			flag=true;
			break;
		}
	}
	if(flag==false)printf("IMPOSSIBLE");
	return 0;
}