Advertisement
Guest User

SGU 103

a guest
Jan 10th, 2014
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.96 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <sstream>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <cmath>
  8.  
  9. #include <vector>
  10. #include <string>
  11. #include <cstring>
  12. #include <set>
  13. #include <queue>
  14. #include <deque>
  15. #include <map>
  16. #include <bitset>
  17. #include <list>
  18.  
  19. #include <functional>
  20. #include <numeric>
  21. #include <cassert>
  22. #include <ctime>
  23.  
  24. using namespace std;
  25.  
  26. typedef long long ll;
  27. typedef pair<int, int> pii;
  28. typedef vector<int> vi;
  29.  
  30. #define mp make_pair
  31. #define pb push_back
  32. #define rep(i, n) for(int (i) = 0; (i) < (n); ++(i))
  33. #define repr(i, l, r) for(int (i) = (l); (i) < (r); ++(i))
  34. #define clr(t, v) memset((t), (v), sizeof(t))
  35. #define all(x) (x).begin(), (x).end()
  36. #define sz(x) ((int)(x).size())
  37. #define fi first
  38. #define se second
  39.  
  40. #define DEBUG
  41.  
  42.  
  43.  
  44.  
  45. const int maxn = 305;
  46. int N, M;
  47. char ini_c[maxn];
  48. int ini_r[maxn], tb[maxn], tp[maxn];
  49. int G[maxn][maxn];
  50. int dp[maxn];
  51. int pred[maxn];
  52. int test[maxn];
  53. int source, dest;
  54. const int inf = 1e8;
  55.  
  56. int go2(char color, int pos, int m, int n, int inc) {
  57.     clr(test, 0);
  58.     int ctime = 0;
  59.     while(true) {
  60.         if (test[pos])
  61.             return inf;
  62.         if (color == 'B' && 0 <= pos && pos < m)
  63.             return ctime;
  64.         if (color == 'P' && m <= pos && pos < (m+n))
  65.             return ctime;
  66.  
  67.         ctime += inc;
  68.         test[pos] = 1;
  69.         pos = (pos + inc) % (m + n);
  70.     }
  71. }
  72.  
  73. int nextmeet(int curtime, int u, int v) {
  74.     int pos1, pos2;
  75.     int a = tb[u], b = tp[u], m = tb[v], n = tp[v];
  76.     if (ini_c[u] == 'B')
  77.         pos1 = (a - ini_r[u] + curtime) % (a+b);
  78.     else
  79.         pos1 = (a + b - ini_r[u] + curtime) % (a+b);
  80.  
  81.     if (ini_c[v] == 'B')
  82.         pos2 = (m - ini_r[v] + curtime) % (m+n);
  83.     else
  84.         pos2 = (m + n - ini_r[v] + curtime) % (m+n);
  85.  
  86.     int t1 = pos1, t2 = pos2;
  87.     rep(i, a+b) {
  88.         if (0 <= t1 && t1 < a && 0 <= t2 && t2 < m)
  89.             return curtime + i;
  90.         if (a <= t1 && t1 < (a+b) && m <= t2 && t2 < (m+n))
  91.             return curtime + i;
  92.         t1 = (t1 + 1) % (a+b);
  93.         t2 = (t2 + 1) % (m+n);
  94.     }
  95.  
  96.     int c1, c2, c3, c4;
  97.  
  98.     rep(i, a+b)
  99.         if ((pos1 + i)%(a+b) == 0) {
  100.             c1 = i;
  101.         }
  102.  
  103.     rep(i, a+b)
  104.         if ((pos1 + i)%(a+b) == a) {
  105.             c2 = i;
  106.         }
  107.  
  108.     rep(i, m+n)
  109.         if ((pos2 + i)%(m+n) == 0) {
  110.             c3 = i;
  111.         }
  112.  
  113.     rep(i, m+n)
  114.         if ((pos2 + i)%(m+n) == m) {
  115.             c4 = i;
  116.         }
  117.  
  118.     int tmpmin = inf;
  119.     tmpmin = min(tmpmin, curtime + c1 + go2('B', (pos2 + c1)%(m+n), m, n, a+b));
  120.     tmpmin = min(tmpmin, curtime + c2 + go2('P', (pos2 + c2)%(m+n), m, n, a+b));
  121.     tmpmin = min(tmpmin, curtime + c3 + go2('B', (pos1 + c3)%(a+b), a, b, m+n));
  122.     tmpmin = min(tmpmin, curtime + c4 + go2('P', (pos1 + c4)%(a+b), a, b, m+n));
  123.     return tmpmin;
  124. }
  125.  
  126. void go() {
  127.     rep(i, N)
  128.         dp[i] = inf;
  129.     dp[source] = 0;
  130.     rep(i, N) {
  131.         pred[i] = i;
  132.     }
  133.     priority_queue<pii, vector<pii>, greater<pii> > Q;
  134.     Q.push(mp(0, source));
  135.     while (!Q.empty()) {
  136.         int time = Q.top().fi, cur = Q.top().se;
  137.         Q.pop();
  138.         if (time > dp[cur])
  139.             continue;
  140.         if (cur == dest)
  141.             return; //early exit
  142.         rep(v, N) {
  143.             if (G[cur][v] != 0) {
  144.                 if (v == pred[cur] || v == cur) continue;
  145.                 int nxt = nextmeet(time, cur, v);
  146.                 if (nxt == inf)
  147.                     continue;
  148.                 if (nxt + G[cur][v] < dp[v]) {
  149.                     pred[v] = cur;
  150.                     Q.push(mp(nxt + G[cur][v], v));
  151.                     dp[v] = nxt + G[cur][v];
  152.                 }
  153.             }
  154.         }
  155.     }
  156.     return;
  157. }
  158.  
  159.  
  160. int main() {
  161. #ifdef DEBUG
  162.     freopen("in.txt", "r", stdin);
  163.     //freopen("out.txt", "w", stdout);
  164. #endif
  165.     ios_base::sync_with_stdio(false);
  166.     scanf("%d%d", &source, &dest);
  167.     source--; dest--;
  168.     scanf("%d%d\n", &N, &M);
  169.  
  170.     rep(i, N)
  171.         scanf("%c%d%d%d\n", &ini_c[i], &ini_r[i], &tb[i], &tp[i]);
  172.  
  173.     rep(i, M) {
  174.         int a, b; scanf("%d%d", &a, &b); a--; b--;
  175.         scanf("%d", &G[a][b]);
  176.         G[b][a] = G[a][b];
  177.     }
  178.  
  179.     go();
  180.     if (pred[dest] == dest) {
  181.         printf("0\n");
  182.         return 0;
  183.     }
  184.     printf("%d\n", dp[dest]);
  185.     //make vector to print in order, etc.
  186.     vector<int> v1;
  187.     while(pred[dest] != dest) {
  188.         v1.push_back(dest);
  189.         dest = pred[dest];
  190.     }
  191.     printf("%d", source+1);
  192.     rep(i, sz(v1))
  193.         printf(" %d", v1[sz(v1)-i-1] + 1);
  194.  
  195.     putchar('\n');
  196.  
  197.     return 0;
  198. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement