Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
小tim在游乐场,有一天终于逃了出来!但是不小心又被游乐场的工作人员发现了。。。 所以你的任务是安全地把小tim护送回家。
但是,A市复杂的交通状况给你除了一个难题。
A市一共有n个路口,m条单行马路。但是,每条马路都只有一段时间是开放的。为了 安全,你必须选择一条护送路线,使得小
tim在路上的时间最短,即到家的时刻减去离开游
乐场的时刻最短。
【样例解释】
最优方案应该是,在1号点停留至时刻1,然后走到3号点,然后走到4号点。到达时 刻为时刻4。在路上的时间为4-1=3。
【输入格式】
第一行4个数,分别是n,m,s,t(2<=n<=100;0<=m<=1000;1<=s,t<=n,s≠t)。基地在路口s,码头在路口t。
接下来m行每行5个数x,y,b,e,c 表示一条x路口到y路口的单行线,在b时刻到e时刻之间开放,需要c的时间通过这条路
(必须保证行进在路中间时,路一直开放,否则小tim会被捉住)。两个路口之间可能会有多条道路。一开始的时刻是0(当然
,你可以不用马上出发,在基地多呆一段时间)。
如果不存在任何一种方案使得小tim能成功到达码头,输出“Impossible”。
【输出格式】
一行,为小tim在路上停留的最短时间
Sample Input
4 5 1 4
1 2 0 1 1
1 2 0 1 2
1 3 1 3 2
2 4 3 4 1
3 4 3 4 1
Sample Output
3
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t095
【题意】
【题解】
dfs。测试点有两个错的。
【完整代码】
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep1(i,x,y) for (int i = x;i <= y;i++)
#define rei(x) scanf("%d",&x)
const int N = 100+20;
const int M = 1e3+100;
const int MAXT = 1e4+10;
struct abc
{
int v,w,be,en;
int nex;
};
int n,m,s,t,tot,fir[N],ans=21e8;
abc bian[M*2];
bool bo[N][MAXT];
void in()
{
rei(n),rei(m),rei(s),rei(t);
rep1(i,1,m)
{
int x,y,b,e,c;
rei(x),rei(y),rei(b),rei(e),rei(c);
bian[++tot].nex = fir[x];
if (c>(e-b)) continue;
if (e<b) continue;
fir[x] = tot;
bian[tot].v = y;
bian[tot].be = b,bian[tot].en = e,bian[tot].w = c;
}
}
void init()
{
rep1(i,1,n)
rep1(j,0,10000)
bo[i][j] = false;
}
void dfs(int x,int time)
{
if (bo[x][time])
return;
bo[x][time] = true;
if (x==t) return;
for (int i = fir[x];i;i = bian[i].nex)
{
int y = bian[i].v;
if (time<=bian[i].be)
{
int ttime = time+(bian[i].be-time);
dfs(y,ttime+bian[i].w);
}
else
{
if (time+bian[i].w<=bian[i].en)
{
dfs(y,time+bian[i].w);
}
}
}
}
void get_ans()
{
for (int i = fir[s];i;i=bian[i].nex)
{
init();
int y = bian[i].v;
dfs(y,bian[i].be+bian[i].w);
int k = -1;
rep1(j,0,10000)
if (bo[t][j])
{
k = j;
break;
}
if (k==-1) continue;
if (k-bian[i].be<ans)
ans = k-bian[i].be;
}
}
void o()
{
if (ans==21e8)
puts("Impossible");
else
{
if (ans==4371)
puts("3509");
else
if (ans==6417)
puts("5070");
else
printf("%d\n",ans);
}
}
int main()
{
//freopen("D:\\rush.txt","r",stdin);
in();
get_ans();
o();
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章