Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <iomanip>
- #include <set>
- #include <map>
- #include <queue>
- #include <ctime>
- #include <cstring>
- #include <stack>
- using namespace std;
- #define endl '\n'
- struct ed { // ребро
- int u; // начало
- int v; // конец
- int w; // вес
- int lu; // длина отрезка одного типа от начала
- int lv; // длина отрезка одного типа от конца
- int mxl; // длина наибольшего освещённого участка
- bool uu; // освещён ли первый отрезок от начала
- bool vv; // освещён ли первый отрезок от конца
- bool hs; // есть ли хоть один неосвещённый отрезок
- };
- vector<pair<int,ed> > G[333];
- int D[333][333];
- int HS[333]; // какое "время под солнцем" можем получить, если стоим в вершине v
- int main( void ) {
- int n,m,T,source,dest;
- queue<pair<int,int> > Q;
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- freopen( "input.txt", "r", stdin ); freopen( "output.txt", "w", stdout );
- for (int i = 0; i < 333; i++) { for (int j = 0; j < 333; j++) { D[i][j] = 1500000000; } }
- cin >> n >> m >> T >> source >> dest;
- for (int i = 0; i < m; i++) {
- int u,v,k;
- int w = 0,lu = 0,lv = 0,mxl = 0;
- bool uu,vv,hs = false;
- bool ok1 = true;
- ed e;
- cin >> u >> v >> k;
- for (int j = 0; j < k; j++) {
- int t,l;
- cin >> l >> t;
- if (ok1 && t) {
- lu += l;
- } else {
- ok1 = false;
- }
- if (t) {
- lv += l;
- } else {
- lv = 0;
- }
- mxl = max(mxl, lv);
- if (j == 0) uu = t;
- if (j == k-1) vv = t;
- if (!t) {
- hs = true;
- }
- w += l;
- }
- e.u = u, e.v = v, e.w = w, e.lu = lu, e.lv = lv, e.mxl = mxl, e.uu = uu, e.vv = vv, e.hs = hs;
- G[u].push_back(make_pair(v,e));
- swap(e.u, e.v), swap(e.lu, e.lv), swap(e.uu, e.vv);
- G[v].push_back(make_pair(u,e));
- }
- for (int i = 1; i <= n; i++) {
- HS[i] = 1500000000;
- for (int j = 0; j < (int)G[i].size(); j++) {
- ed & e = G[i][j].second;
- if (e.uu) {
- if (e.hs) {
- HS[i] = min(HS[i],e.lu);
- }
- } else {
- HS[i] = 0;
- }
- }
- }
- D[source][0] = 0;
- Q.push(make_pair(source,0));
- while (Q.size()) {
- int v = Q.front().first, t = Q.front().second;
- int dd = D[v][t];
- Q.pop();
- for (int i = 0; i < (int)G[v].size(); i++) {
- int vv = G[v][i].first;
- ed & e = G[v][i].second;
- int nt = (e.hs ? e.lv*e.vv : t+e.w);
- if (e.uu && e.lu+t > T) continue;
- if (e.mxl > T) continue;
- if (nt > T) continue;
- if (D[vv][nt] > dd+e.w) {
- D[vv][nt] = dd+e.w;
- Q.push(make_pair(vv,nt));
- }
- }
- if (HS[v]+t <= T && t > HS[v]) {
- t = HS[v];
- for (int i = 0; i < (int)G[v].size(); i++) {
- int vv = G[v][i].first;
- ed & e = G[v][i].second;
- int nt = (e.hs ? e.lv*e.vv : t+e.w);
- if (e.uu && e.lu+t > T) continue;
- if (e.mxl > T) continue;
- if (nt > T) continue;
- if (D[vv][nt] > dd+e.w+2*HS[v]) {
- D[vv][nt] = dd+e.w+2*HS[v];
- Q.push(make_pair(vv,nt));
- }
- }
- }
- }
- int ans = 1500000000;
- for (int i = 0; i <= T; i++) {
- ans = min(ans, D[dest][i]);
- }
- if (ans >= 1500000000) ans = -1;
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment