1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <queue> 5 using namespace std; 6  7 const int maxn = 300 + 5; 8  9 struct Edge {10     int from, to, open, close, needTime;11     Edge(int from, int to, int open, int close, int needTime):12         from(from), to(to), open(open), close(close), needTime(needTime) {}13 };14 15 struct HeapNode {16     int d, u;17     bool operator < (const HeapNode& rhs) const {18         return d > rhs.d;19     }20 };21 22 struct Dijkstra {23     int n, m;24     vector<Edge> edges;25     vector<int> G[maxn];26     bool vis[maxn];27     int d[maxn];28 29     void init(int n) {30         this -> n = n;31         for (int i = 0; i < n; i++) G[i].clear();32         edges.clear();33     }34 35     void AddEdge(int from, int to, int open, int close, int needTime) {36         edges.push_back(Edge(from, to, open, close, needTime));37         m = edges.size();38         G[from].push_back(m - 1);39     }40 41     bool check(int ut, int& vt, Edge e) {42         if (e.needTime > e.open) return false;43         int T = e.open + e.close;44         if (ut % T + e.needTime > e.open)45             ut += T - (ut % T);46         if (ut + e.needTime < vt) {47             vt = ut + e.needTime;48             return true;49         }50         return false;51     }52 53     int dijkstra(int s, int t) {54         memset(vis, 0, sizeof(vis));55         memset(d, 0x3f, sizeof(d));56         priority_queue<HeapNode> q;57         d[s] = 0;58         q.push((HeapNode){0, s});59         while (!q.empty()) {60             int u = q.top().u; q.pop();61             if (vis[u]) continue; vis[u] = 1;62             if (u == t) break;63             for (int i = 0; i < G[u].size(); i++) {64                 Edge& e = edges[G[u][i]];65                 if (check(d[u], d[e.to], e)) q.push((HeapNode){d[e.to], e.to});66             }67         }68         return d[t];69     }70 };71 72 Dijkstra dij;73 int n, m, s, t;74 75 int main() {76     int kase = 0;77     while (scanf("%d%d%d%d", &n, &m, &s, &t) == 4) {78         dij.init(n);79         int u, v, a, b, t2;80         while (m--) {81             scanf("%d%d%d%d%d", &u, &v, &a, &b, &t2);82             dij.AddEdge(u - 1, v - 1, a, b, t2);83         }84         printf("Case %d: %d\n", ++kase, dij.dijkstra(s - 1, t - 1));85     }86     return 0;87 }