daily pastebin goal
21%
SHARE
TWEET

SGU 103

a guest Jan 10th, 2014 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand