POJ3594-枚举+spfa

灰太狼 2022-07-12 04:51 145阅读 0赞

Escort of Dr. Who How

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;2653</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;699</td> 
  </tr> 
 </tbody> 
</table>

Description

The notorious ringleader and cyber-criminal Derek Wu, better known as Dr. Who How, has been convicted for multiple abductions and cyber-frauds several minutes ago. He will soon be transferred from the court to the prison to serve a life sentence. Intelligence from undercover officers in Dr. Who How’s outlawed gang indicates a possible forcible rescue operation by gang members in the case that Dr. Who How is convicted. To ensure a successful escort, besides adopting enhanced security measures, the police force further desires to minimize the escort time—the time that the motorcade of escort has to spend between departure from the court and arrival at the prison.

The complex traffic condition in the city imposes complications on the police force’s escort effort. While the municipal government has agreed to temporarily shut down a few roads for exclusive police use, the shut-down time windows vary among roads and are generally narrow to avoid excessively disturbing the life of the citizens. The motorcade of escort must pass through any road entirely within its shut-down time window and not use any road that the municipal government has not agreed to shut down.

Given information about all roads available to the police force for the escort, determine the shortest escort time.

Input

The input contains a single test case. The first line contains four integers *n*, *m*, *s* and *t* (2 ≤ *n* ≤ 100; 0 ≤ *m* ≤ 1000; 1 ≤ *s*, *t* ≤ *n*; *s* ≠ *t*). There are *n* junctions, some pairs of which are connected by *m*roads. The court and the prison are located at the *s*\-th and the *t*\-th junctions, respectively. The next *m* lines each contain five integers *x*, *y*, *b*, *e* and *c* (1 ≤ *x*, *y* ≤ *n*; 0 ≤ *b* < *e* ≤ 104; 1 ≤ *c* ≤ 104), indicating that the directed lanes running from the *x*\-th junction to the *y*\-th junction of a road that takes the motorcade of escort *c* units of time to pass through will be shut down between time *b*and *e*. The earliest time when the motorcade can leave the court is time 0.

Output

If the escort is possible, print the shortest escort time; otherwise, print “Impossible”.

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

Hint

The sample is depicted in Figure 1. Each junction is represented by a numbered spot. Each road is represented by an arrow labeled with ![\\langle\\langle b,e\\rangle,c\\rangle][langle_langle b_e_rangle_c_rangle], its shut-down time window and pass-through time.

![3594_1.png][]

Figure 1: Depiction of the sample

The second road listed in the sample is virtually unusable for it takes the motorcade of escort longer time to pass through than it can stay available. The remaining four roads enable the following two escort routes:

1.  ![1\\stackrel\{\\!\\langle 0,1\\rangle\}\{\\to\}2\\stackrel\{\\!\\langle 3,4\\rangle\}\{\\to\}4][1_stackrel_langle 0_1_rangle_to_2_stackrel_langle 3_4_rangle_to_4]
2.  ![1\\stackrel\{\\!\\langle 1,3\\rangle\}\{\\to\}3\\stackrel\{\\!\\langle 3,4\\rangle\}\{\\to\}4][1_stackrel_langle 1_3_rangle_to_3_stackrel_langle 3_4_rangle_to_4]

(The label ![\\langle s,t\\rangle][langle s_t_rangle] over an arrow indicates that the motorcade passes through the corresponding road between time *s* and *t*.) The first route takes four units of escort time, whereas the second takes three, which is the shortest possible.

**题目大意**：

给你一张n个点m条边的无向图，每条边有一个允许通过的时间段以及通过所花费的时间求从起点1到终点n所花费的最小时间起始时间是0，并且允许在某一个点停留

**题目思路：**

首先根据题目的限制条件我们可以得知当边权大于开放的时间段时这条边就不能用，其次是走到当前点的时间加上到达下一 个点边权大于开放的最后时刻或起始时间早于开放时刻时不能走，对于第二种情况我们可以等到开放再走，所以我们可以用 spfa算最短路 但是这里题目有个坑就是如果在起始时间0等待的时间不算入总的花费的时间，所以我们必须枚举起始时间， 然后最后的总的花费在减去起始时间就是该时刻出发的最短路！

**AC代码：**

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    
    using namespace std;
    
    const int inf = 1e8;
    
    struct st{
        int v,w,s,t,nex;
    }edge[1005];
    
    int n,m,s,t,e;
    
    int hed[105],vis[105],dis[105];
    
    void add(int u,int v,int x,int y,int w){
        edge[e].v=v,edge[e].w=w ,edge[e].s=x,edge[e].t=y,edge[e].nex = hed[u],hed[u]=e++;
    }
    
    int spfa(int ti){
        for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
        dis[s]=ti,vis[s]=1;
        queue<int>q;
        q.push(s);
        while(!q.empty()){
            int u = q.front();q.pop();vis[u]=0;
            for(int i = hed[u];~i;i=edge[i].nex){
                int v = edge[i].v;
                int c = dis[u];
                dis[u]=max(dis[u],edge[i].s);
                if(dis[u]+edge[i].w<=edge[i].t)
                if(dis[v]>dis[u]+edge[i].w){
                    dis[v]=dis[u]+edge[i].w;
                    if(!vis[v]){
                        q.push(v);
                        vis[v]=1;
                    }
                }
                dis[u]=c;
            }
        }
        if(dis[t]!=inf)dis[t]-=ti;
        return dis[t];
    }
    
    int main()
    {
        cin>>n>>m>>s>>t;
        memset(hed,-1,sizeof(hed));
        e=1;
        int Min = inf,Max=0;
    
        while(m--){
            int a,b,c,d,e;scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
            if(d-c<e)continue;
            Min=min(Min,c);
            Max=max(Max,d);
            add(a,b,c,d,e);
        }
        int ans = inf;
        for(int i=Min;i<Max;i++)           //枚举起始时间
           ans=min(ans,spfa(i));
        if(ans==inf)cout<<"Impossible"<<endl;
        else cout<<ans<<endl;
        return 0;
    }

[langle_langle b_e_rangle_c_rangle]: http://poj.org/formula?tex=%5Clangle%5Clangle+b%2Ce%5Crangle%2Cc%5Crangle
[3594_1.png]: /images/20220711/89644f105ed242e4b3258de512a566af.png
[1_stackrel_langle 0_1_rangle_to_2_stackrel_langle 3_4_rangle_to_4]: http://poj.org/formula?tex=1%5Cstackrel%7B%5C%21%5Clangle+0%2C1%5Crangle%7D%7B%5Cto%7D2%5Cstackrel%7B%5C%21%5Clangle+3%2C4%5Crangle%7D%7B%5Cto%7D4
[1_stackrel_langle 1_3_rangle_to_3_stackrel_langle 3_4_rangle_to_4]: http://poj.org/formula?tex=1%5Cstackrel%7B%5C%21%5Clangle+1%2C3%5Crangle%7D%7B%5Cto%7D3%5Cstackrel%7B%5C%21%5Clangle+3%2C4%5Crangle%7D%7B%5Cto%7D4
[langle s_t_rangle]: http://poj.org/formula?tex=%5Clangle+s%2Ct%5Crangle