题目描述：求从s到t的最短路。给你的条件是每条路在哪些时间可以通过还有通过需要的时间是多少。

解题报告：

限制条件最短路（本解题报告使用方法）

d[i][j]表示出发时间为i，目的地为j的最短时间是多少，dij即可。

代码如下：

#include<iostream>
#include<queue>
using namespace std;
struct edge{int b, e, to, val, next;}jeo[2000];
int v[102], cnt, n, m, s, t, d[10001][102];
bool vst[10001][102];
void insert(int from, int to, int val, int b, int e)
{
    jeo[cnt].to = to, jeo[cnt].b = b, jeo[cnt].e = e, jeo[cnt].val = val;
    jeo[cnt].next = v[from]; v[from] = cnt++;
}
struct pint
{
    int sta, len, id;
    pint(int sta, int len, int id):sta(sta), len(len), id(id){}
    friend bool operator < (pint a, pint b)
    {
        if (a.len - a.sta == b.len - b.sta)
            return a.len > b.len;
        return a.len - a.sta > b.len - b.sta;
    }
};
int dij(int from, int to, int n)
{
    int mm = -1;
    for(int i = v[from]; i != -1; i = jeo[i].next) mm = max(mm, jeo[i].e - jeo[i].val);
    for(int i = 0; i <= mm; i++)
        for(int j = 1; j <= n; j++) vst[i][j] = 0, d[i][j] = 0x7fffffff;
    priority_queue<pint> heap;
    for(int i = 0; i <= mm; i++)
        for(int j = v[from]; j != -1; j = jeo[j].next)
        {
            if (i >= jeo[j].b && i + jeo[j].val <= jeo[j].e)
                heap.push(pint(i, i + jeo[j].val, jeo[j].to)), d[i][jeo[j].to] = min(d[i][jeo[j].to], jeo[j].val);
        }
    int ans = 0x7fffffff;
    while(!heap.empty())
    {
        pint tmp = heap.top(); heap.pop();
        if (tmp.id == to) {ans = min(ans, d[tmp.sta][tmp.id]);}
        if (vst[tmp.sta][tmp.id]) continue;
        vst[tmp.sta][tmp.id] = 1;
        for(int i = v[tmp.id]; i != -1; i = jeo[i].next)
        {
            if (tmp.len + jeo[i].val <= jeo[i].e && max(jeo[i].b, tmp.len) + jeo[i].val - tmp.sta < d[tmp.sta][jeo[i].to])
            {
                d[tmp.sta][jeo[i].to] = max(jeo[i].b, tmp.len) + jeo[i].val - tmp.sta;
                heap.push(pint(tmp.sta, max(jeo[i].b, tmp.len) + jeo[i].val, jeo[i].to));
            }
        }
    }
    if (ans == 0x7fffffff) return -1;
    else return ans;
}
int main()
{
    while(scanf("%d%d%d%d", &n, &m, &s, &t) != EOF)
    {
        memset(v, -1, sizeof(int) * (n + 1)); cnt = 0;
        while(m--)
        {
            int from, to, val, b, e;
            scanf("%d%d%d%d%d", &from, &to, &b, &e, &val);
            if (e - b >= val) insert(from, to, val, b, e);
        }
        int ans = dij(s, t, n);
        if (ans == -1) printf("Impossible\n");
        else printf("%d\n", ans);
    }
    return 0;
}