Guest User

Untitled

a guest
Oct 5th, 2014
366
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <iomanip>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <ctime>
  12. #include <cstring>
  13. #include <stack>
  14.  
  15. using namespace std;
  16.  
  17. #define endl    '\n'
  18.  
  19. struct ed {    // ребро
  20.     int u;     // начало
  21.     int v;     // конец
  22.     int w;     // вес
  23.     int lu;    // длина отрезка одного типа от начала
  24.     int lv;    // длина отрезка одного типа от конца
  25.     int mxl;   // длина наибольшего освещённого участка
  26.     bool uu;   // освещён ли первый отрезок от начала
  27.     bool vv;   // освещён ли первый отрезок от конца
  28.     bool hs;   // есть ли хоть один неосвещённый отрезок
  29. };
  30.  
  31. vector<pair<int,ed> > G[333];
  32. int D[333][333];
  33. int HS[333];   // какое "время под солнцем" можем получить, если стоим в вершине v
  34.  
  35. int main( void ) {
  36.     int n,m,T,source,dest;
  37.     queue<pair<int,int> > Q;
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     freopen( "input.txt", "r", stdin ); freopen( "output.txt", "w", stdout );
  41.     for (int i = 0; i < 333; i++) { for (int j = 0; j < 333; j++) { D[i][j] = 1500000000; } }
  42.     cin >> n >> m >> T >> source >> dest;
  43.     for (int i = 0; i < m; i++) {
  44.         int u,v,k;
  45.         int w = 0,lu = 0,lv = 0,mxl = 0;
  46.         bool uu,vv,hs = false;
  47.         bool ok1 = true;
  48.         ed e;
  49.         cin >> u >> v >> k;
  50.         for (int j = 0; j < k; j++) {
  51.             int t,l;
  52.             cin >> l >> t;
  53.             if (ok1 && t) {
  54.                 lu += l;
  55.             } else {
  56.                 ok1 = false;
  57.             }
  58.             if (t) {
  59.                 lv += l;
  60.             } else {
  61.                 lv = 0;
  62.             }
  63.             mxl = max(mxl, lv);
  64.             if (j == 0) uu = t;
  65.             if (j == k-1) vv = t;
  66.             if (!t) {
  67.                 hs = true;
  68.             }
  69.             w += l;
  70.         }
  71.         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;
  72.         G[u].push_back(make_pair(v,e));
  73.         swap(e.u, e.v), swap(e.lu, e.lv), swap(e.uu, e.vv);
  74.         G[v].push_back(make_pair(u,e));
  75.     }
  76.     for (int i = 1; i <= n; i++) {
  77.         HS[i] = 1500000000;
  78.         for (int j = 0; j < (int)G[i].size(); j++) {
  79.             ed & e = G[i][j].second;
  80.             if (e.uu) {
  81.                 if (e.hs) {
  82.                     HS[i] = min(HS[i],e.lu);
  83.                 }
  84.             } else {
  85.                 HS[i] = 0;
  86.             }
  87.         }
  88.     }
  89.     D[source][0] = 0;
  90.     Q.push(make_pair(source,0));
  91.     while (Q.size()) {
  92.         int v = Q.front().first, t = Q.front().second;
  93.         int dd = D[v][t];
  94.         Q.pop();
  95.         for (int i = 0; i < (int)G[v].size(); i++) {
  96.             int vv = G[v][i].first;
  97.             ed & e = G[v][i].second;
  98.             int nt = (e.hs ? e.lv*e.vv : t+e.w);
  99.             if (e.uu && e.lu+t > T) continue;
  100.             if (e.mxl > T) continue;
  101.             if (nt > T) continue;
  102.             if (D[vv][nt] > dd+e.w) {
  103.                 D[vv][nt] = dd+e.w;
  104.                 Q.push(make_pair(vv,nt));
  105.             }
  106.         }
  107.         if (HS[v]+t <= T && t > HS[v]) {
  108.             t = HS[v];
  109.             for (int i = 0; i < (int)G[v].size(); i++) {
  110.                 int vv = G[v][i].first;
  111.                 ed & e = G[v][i].second;
  112.                 int nt = (e.hs ? e.lv*e.vv : t+e.w);
  113.                 if (e.uu && e.lu+t > T) continue;
  114.                 if (e.mxl > T) continue;
  115.                 if (nt > T) continue;
  116.                 if (D[vv][nt] > dd+e.w+2*HS[v]) {
  117.                     D[vv][nt] = dd+e.w+2*HS[v];
  118.                     Q.push(make_pair(vv,nt));
  119.                 }
  120.             }
  121.         }
  122.     }
  123.     int ans = 1500000000;
  124.     for (int i = 0; i <= T; i++) {
  125.         ans = min(ans, D[dest][i]);
  126.     }
  127.     if (ans >= 1500000000) ans = -1;
  128.     cout << ans << endl;
  129.     return 0;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment