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

## 有没有好好看题，忘了Impossible了。惩罚我，贴上我蒟蒻的代码 100+ms SFPA

Posted by proverbs at 2012-09-25 22:58:54 on Problem 3594 and last updated at 2012-09-25 23:01:59
```#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#define N 200
#define M 20000
using namespace std;
struct Q
{
int md,ft;
}q[M*N];
int cnt,n,m,S,T,mtime;
bool vis[N][M];
inline void add(int u,int v,int w,int l,int r)
{
}
{
for(int i=1,a,b,c,d,e;i<=m;i++)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
}
}
void spfa()
{
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
int h=1,t=1,ans=0x7f7f7f7f;
mtime=0;
for(int i=0;i<=mtime;i++)
if(i>=lt[j]&&i<=rt[j]-len[j])
dis[to[j]][i]=min(dis[to[j]][i],i+len[j]);//处理出所有与S相连的点的状态

for(int i=0;i<=mtime;i++)
if(i>=lt[j]&&i<=rt[j]-len[j])
if(!vis[to[j]][i]&&dis[to[j]][i]==len[j]+i)
{
vis[to[j]][i]=true;
q[t].md=to[j]; q[t].ft=i; t++;//入队
}
while(h<t)
{
Q sta=q[h++];
vis[sta.md][sta.ft]=false;
if(sta.md==T) ans=min(ans,dis[sta.md][sta.ft]-sta.ft);
{
int tmp=max(lt[i],dis[sta.md][sta.ft])+len[i];
if(tmp<=rt[i]&&tmp<dis[to[i]][sta.ft])
{
dis[to[i]][sta.ft]=tmp;
if(!vis[to[i]][sta.ft])
{
vis[to[i]][sta.ft]=true;
q[t].md=to[i]; q[t].ft=sta.ft; t++;
}
}
}
}
for(int i=0;i<=mtime;i++)
if(dis[T][i]<999999) ans=min(ans,dis[T][i]-i);
if(ans>999999) printf("Impossible\n");
else printf("%d\n",ans);
//dis[i][j]表示从j时刻出发到达i点最小的“时刻”！
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&S,&T)!=EOF)
{
if(S==T) puts("0");
else spfa();
}
return 0;
}
```

Followed by: