【t095】拯救小tim
阅读原文时间:2023年10月02日阅读:3

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;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章