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

## 谁能帮忙看下，我枚举开始时间+bfs老是wa和Tle之间

Posted by ccnuzhang at 2008-09-02 20:49:07 on Problem 3594
```#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int size=105,inf=1000000000;

typedef struct Path
{
int v,w;
int b,e;
}Path;

typedef struct Data
{
int v;
int time;
}Data;

bool operator < (Data a,Data b)
{
return a.time>b.time;
}

priority_queue<Data>Q;
vector<Path> path[size];
int N,M,num[size],mtime[size],nn[size];

int BFS(int s,int t,int j,int min)
{
int v,i;
while(!Q.empty()) Q.pop();
for(i=1;i<=N;i++)
mtime[i]=inf;
Data q,np;
q.time=j;
q.v=s;
mtime[s]=j;
Q.push(q);
/*	for(i=0;i<path[s].size();i++)
if(q.time>=path[s][i].b && q.time+path[s][i].w<=path[s][i].e)
{
np.time=q.time+path[s][i].w;
np.v=path[s][i].v;
if(np.time<mtime[np.v])
{
mtime[np.v]=np.time;
Q.push(np);
}
}*/
while(!Q.empty())
{
q=Q.top();
Q.pop();
v=q.v;
if(v==t) return q.time-j;
for(i=0;i<path[v].size();i++)
if(q.time>=path[v][i].b && q.time+path[v][i].w<=path[v][i].e)
{
np.time=q.time+path[v][i].w;
np.v=path[v][i].v;
if(np.time<mtime[np.v])
{
mtime[np.v]=np.time;
Q.push(np);
}
}
q.time++;
if( q.time<num[v])
{
Q.push(q);
}
}
return inf;
}
int Slove(int s,int t)
{
int i,j,min=inf,len=0,temp;
for(i=0;i<path[s].size();i++)
{
temp=path[s][i].e-path[s][i].w;
if(temp>=0) nn[len++]=temp;
}
sort(nn,nn+len);
for(i=1,j=0;i<len;i++)
{
if(nn[i]==nn[j]) continue;
nn[++j]=nn[i];
}
len=j;
for(i=0;i<=len;i++)
{
temp=BFS(s,t,nn[i],min);
if(temp<min) min=temp;
}
return min;
}
int main()
{
int s,t,i;
int u;
Path q;
scanf("%d%d%d%d",&N,&M,&s,&t);
for(i=1;i<=N;i++)
num[i]=0;
while(M--)
{
scanf("%d%d%d%d%d",&u,&q.v,&q.b,&q.e,&q.w);
if(num[u]<q.e) num[u]=q.e;
path[u].push_back(q);
}
i=Slove(s,t);
if(i==inf) printf("Impossible\n");
else printf("%d\n",i);
return 12;
}
```

Followed by: