#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;
#define INF   1000000000
#define Max(a, b)  ((a > b) ? (a) : (b))


struct EDGE
{
	int v;
	int st, et, ct;
	EDGE(){}
	EDGE(int v0, int s0, int e0, int c0):v(v0),st(s0),et(e0),ct(c0){}
};

int n, m, start, end;
vector<EDGE> path[102];
deque<int> Q[2];
int dp[102];

bool init()
{
	for (int i = 0; i <= n; i++)
	{
		path[i].clear();
	}
	return true;
}

bool Input()
{
	int u, v, s, e, c;
	
	scanf("%d %d %d %d", &n, &m, &start, &end);

	init();
	
	for (int i = 0 ; i < m; i++)
	{
		scanf("%d %d %d %d %d",&u, &v, &s, &e, &c);
		if (s + c > e)
			continue;

		path[u].push_back(EDGE(v, s, e, c));
	}
	return true;
}

bool bfs()
{
	int now = 0, u, len;
	EDGE edge;
	
	while(!Q[now].empty())
	{
		Q[1 - now].clear();
		while(!Q[now].empty())
		{
			u = Q[now].front();
			Q[now].pop_front();
			
			len = path[u].size();
			for (int i = 0 ; i < len; i++)
			{
				edge = path[u][i];
				int ReachTime = Max(dp[u] + edge.ct, edge.st + edge.ct);
				if (ReachTime > edge.et)
					continue;

				if (ReachTime < dp[edge.v])
				{
					dp[edge.v] = ReachTime;
					if (end == edge.v)
						continue;
					Q[1-now].push_back(edge.v);
				}
			}
		}
		now = 1 - now;
	}
	return true;
}
void clear()
{
	Q[0].clear();
	Q[1].clear();
	for (int i = 0; i <= n; i++)
	{
		dp[i]  = INF;
	}
}

bool Run()
{
	EDGE edge;
	int ans = INF;
	int len = path[start].size();

	for (int i = 0; i < len; i++)
	{	
		clear();
		
		edge  =  path[start][i];
		dp[edge.v] = edge.st + edge.ct;
		Q[0].push_back(edge.v);

		bfs();

		if (dp[end] != INF)
		{
			dp[end] -= edge.st;
			if (dp[end]  < ans)
				ans = dp[end];
		}
	}
	
	if (INF == ans)
		printf("Impossible\n");
	else
		printf("%d\n", ans);
	
	return true;
}

int main()
{
	Input();
	Run();
	return 0;
}

• Re:谁能帮忙看一下这代码的思想对不对！谢谢了 (15) tibelf 2008-05-12 10:55:48
  • Re:谁能帮忙看一下这代码的思想对不对！谢谢了 (7) repeat 2008-05-12 10:57:40