Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 谁能帮忙看一下这代码的思想对不对！谢谢了

Posted by repeat at 2008-05-12 10:49:49 on Problem 3594
```#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;
}```

Followed by: