1 /**  2  * UVa  3  * Problem#12661  4  * Accepted  5  * Time:50ms  6  */  7 #include<iostream>  8 #include<fstream>  9 #include<sstream> 10 #include<cstdio> 11 #include<cstdlib> 12 #include<cstring> 13 #include<ctime> 14 #include<cctype> 15 #include<cmath> 16 #include<algorithm> 17 #include<stack> 18 #include<queue> 19 #include<set> 20 #include<map> 21 #include<vector> 22 using namespace std; 23 typedef bool boolean; 24 #define smin(a, b)    (a) = min((a), (b)) 25 #define smax(as, b)    (a) = max((a), (b)) 26 template<typename T> 27 inline boolean readInteger(T& u){ 28     char x; 29     int aFlag = 1; 30     while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 31     if(x == -1)    return false; 32     if(x == ‘-‘){ 33         x = getchar(); 34         aFlag = -1; 35     } 36     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - ‘0‘); 37     ungetc(x, stdin); 38     u *= aFlag; 39     return true; 40 } 41  42 typedef class Edge{ 43     public: 44         int end; 45         int next; 46         int open; 47         int close; 48         int t; 49         Edge(const int end = 0, const int next = 0, const int open = 0, const int close = 0, const int t = 0):end(end), next(next), open(open), close(close), t(t){        } 50         int across(int arrived){ 51             int re = arrived % (open + close); 52             if(re >= 0 && re + t <= open)    return     arrived + t; 53             return (arrived / (open + close) + 1) * (open + close) + t; 54         } 55 }Edge; 56  57 typedef class MapManager{ 58     public: 59         int ce; 60         Edge* edges; 61         int* h; 62         MapManager():ce(0), edges(NULL), h(NULL){        } 63         MapManager(int points, int limit):ce(0){ 64             h = new int[(const int)(points + 1)]; 65             edges = new Edge[(const int)(limit + 1)]; 66             memset(h, 0, sizeof(int) * (points + 1)); 67         } 68         inline void addEdge(int from, int end, int open, int close, int t){ 69             if(t > open)    return;        //无法通过  70             edges[++ce] = Edge(end, h[from], open, close, t); 71             h[from] = ce; 72         } 73         Edge& operator [](int pos){ 74             return edges[pos]; 75         } 76         void clear(){ 77             delete[] edges; 78             delete[] h; 79             ce = 0; 80         } 81 }MapManager; 82  83 #define m_begin(g, i)    (g).h[(i)] 84  85 int n, m, from, _end; 86 MapManager g; 87  88 inline boolean init(){ 89     if(!readInteger(n))    return false; 90     readInteger(m); 91     readInteger(from); 92     readInteger(_end); 93     g = MapManager(n, m); 94     for(int i = 1, u, v, a, b, t; i <= m; i++){ 95         readInteger(u); 96         readInteger(v); 97         readInteger(a); 98         readInteger(b); 99         readInteger(t);100         g.addEdge(u, v, a, b, t);101     }102     return true;103 }104 105 boolean* visited;106 queue<int>    que;107 int* f;108 inline int spfa(int s, int t){109     que.push(s);110     visited[s] = true;111     f[s] = 0;112     while(!que.empty()){113         int e = que.front();114         que.pop();115         visited[e] = false;116         for(int i = m_begin(g, e); i != 0; i = g[i].next){117             int& eu = g[i].end;118             int cmp = g[i].across(f[e]);119             if(cmp < f[eu]){120                 f[eu] = cmp;121                 if(!visited[eu] && eu != t){122                     que.push(eu);123                     visited[eu] = true;124                 }125             }126         }127     }128     return f[t];129 }130 131 inline void solve(){132     visited = new boolean[(const int)(n + 1)];133     f = new int[(const int)(n + 1)];134     memset(visited, false, sizeof(boolean) * (n + 1));135     memset(f, 0x7f, sizeof(int) * (n + 1));136     int res = spfa(from, _end);137     printf("%d\n", res);138 }139 140 inline void clear(){141     g.clear();142     delete[] visited;143     delete[] f;144 }145 146 int main(){147     int kase = 1;148     while(init()){149         printf("Case %d: ", kase++);150         solve();151         clear();152     }153     return 0;154 }