Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <iostream>
- #include <sstream>
- #include <algorithm>
- #include <utility>
- #include <cmath>
- #include <vector>
- #include <string>
- #include <cstring>
- #include <set>
- #include <queue>
- #include <deque>
- #include <map>
- #include <bitset>
- #include <list>
- #include <functional>
- #include <numeric>
- #include <cassert>
- #include <ctime>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- #define mp make_pair
- #define pb push_back
- #define rep(i, n) for(int (i) = 0; (i) < (n); ++(i))
- #define repr(i, l, r) for(int (i) = (l); (i) < (r); ++(i))
- #define clr(t, v) memset((t), (v), sizeof(t))
- #define all(x) (x).begin(), (x).end()
- #define sz(x) ((int)(x).size())
- #define fi first
- #define se second
- #define DEBUG
- const int maxn = 305;
- int N, M;
- char ini_c[maxn];
- int ini_r[maxn], tb[maxn], tp[maxn];
- int G[maxn][maxn];
- int dp[maxn];
- int pred[maxn];
- int test[maxn];
- int source, dest;
- const int inf = 1e8;
- int go2(char color, int pos, int m, int n, int inc) {
- clr(test, 0);
- int ctime = 0;
- while(true) {
- if (test[pos])
- return inf;
- if (color == 'B' && 0 <= pos && pos < m)
- return ctime;
- if (color == 'P' && m <= pos && pos < (m+n))
- return ctime;
- ctime += inc;
- test[pos] = 1;
- pos = (pos + inc) % (m + n);
- }
- }
- int nextmeet(int curtime, int u, int v) {
- int pos1, pos2;
- int a = tb[u], b = tp[u], m = tb[v], n = tp[v];
- if (ini_c[u] == 'B')
- pos1 = (a - ini_r[u] + curtime) % (a+b);
- else
- pos1 = (a + b - ini_r[u] + curtime) % (a+b);
- if (ini_c[v] == 'B')
- pos2 = (m - ini_r[v] + curtime) % (m+n);
- else
- pos2 = (m + n - ini_r[v] + curtime) % (m+n);
- int t1 = pos1, t2 = pos2;
- rep(i, a+b) {
- if (0 <= t1 && t1 < a && 0 <= t2 && t2 < m)
- return curtime + i;
- if (a <= t1 && t1 < (a+b) && m <= t2 && t2 < (m+n))
- return curtime + i;
- t1 = (t1 + 1) % (a+b);
- t2 = (t2 + 1) % (m+n);
- }
- int c1, c2, c3, c4;
- rep(i, a+b)
- if ((pos1 + i)%(a+b) == 0) {
- c1 = i;
- }
- rep(i, a+b)
- if ((pos1 + i)%(a+b) == a) {
- c2 = i;
- }
- rep(i, m+n)
- if ((pos2 + i)%(m+n) == 0) {
- c3 = i;
- }
- rep(i, m+n)
- if ((pos2 + i)%(m+n) == m) {
- c4 = i;
- }
- int tmpmin = inf;
- tmpmin = min(tmpmin, curtime + c1 + go2('B', (pos2 + c1)%(m+n), m, n, a+b));
- tmpmin = min(tmpmin, curtime + c2 + go2('P', (pos2 + c2)%(m+n), m, n, a+b));
- tmpmin = min(tmpmin, curtime + c3 + go2('B', (pos1 + c3)%(a+b), a, b, m+n));
- tmpmin = min(tmpmin, curtime + c4 + go2('P', (pos1 + c4)%(a+b), a, b, m+n));
- return tmpmin;
- }
- void go() {
- rep(i, N)
- dp[i] = inf;
- dp[source] = 0;
- rep(i, N) {
- pred[i] = i;
- }
- priority_queue<pii, vector<pii>, greater<pii> > Q;
- Q.push(mp(0, source));
- while (!Q.empty()) {
- int time = Q.top().fi, cur = Q.top().se;
- Q.pop();
- if (time > dp[cur])
- continue;
- if (cur == dest)
- return; //early exit
- rep(v, N) {
- if (G[cur][v] != 0) {
- if (v == pred[cur] || v == cur) continue;
- int nxt = nextmeet(time, cur, v);
- if (nxt == inf)
- continue;
- if (nxt + G[cur][v] < dp[v]) {
- pred[v] = cur;
- Q.push(mp(nxt + G[cur][v], v));
- dp[v] = nxt + G[cur][v];
- }
- }
- }
- }
- return;
- }
- int main() {
- #ifdef DEBUG
- freopen("in.txt", "r", stdin);
- //freopen("out.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- scanf("%d%d", &source, &dest);
- source--; dest--;
- scanf("%d%d\n", &N, &M);
- rep(i, N)
- scanf("%c%d%d%d\n", &ini_c[i], &ini_r[i], &tb[i], &tp[i]);
- rep(i, M) {
- int a, b; scanf("%d%d", &a, &b); a--; b--;
- scanf("%d", &G[a][b]);
- G[b][a] = G[a][b];
- }
- go();
- if (pred[dest] == dest) {
- printf("0\n");
- return 0;
- }
- printf("%d\n", dp[dest]);
- //make vector to print in order, etc.
- vector<int> v1;
- while(pred[dest] != dest) {
- v1.push_back(dest);
- dest = pred[dest];
- }
- printf("%d", source+1);
- rep(i, sz(v1))
- printf(" %d", v1[sz(v1)-i-1] + 1);
- putchar('\n');
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement