Submission #1027035

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

#define INF (1LL<<60)
#define MAX_B 260000
typedef pair<int, int> P;
typedef pair<long long, P> P2;

int N, M, S, D;
vector<P2> edges[253];
long long d[253][MAX_B+1];

int main() {
  cin >> N >> M >> S >> D;
  if (N >= 253) return 1;
  for (int k=0; k<M; k++) {
    int L;
    cin >> L;
    int s[L], w[L];
    for (int i=0; i<L; i++) cin >> s[i];
    for (int i=0; i<L-1; i++) cin >> w[i];

    int t = 0, sum = 0;
    for (int i=0; i<L-1; i++) sum += w[i];

    for (int i=0, g=sum; i<L; i++) {
      int l = 0;
      for (int j=i+1, g2=g; j<L; j++) {
        g2 -= w[j-1];
        l += w[j-1];
        edges[s[i]].push_back(P2(s[j], P(l, g2)));
      }
      g -= w[i];
    }
    for (int i=L-1, g=sum; i>=0; i--) {
      int l = 0;
      for (int j=i-1, g2=g; j>=0; j--) {
        g2 -= w[j];
        l += w[j];
        edges[s[i]].push_back(P2(s[j], P(l, g2)));
      }
      g -= w[i-1];
    }
  }

  for (int i=0; i<N; i++) {
    for (int j=0; j<MAX_B; j++) {
      d[i][j] = INF;
    }
  }

  priority_queue< P2, vector<P2>, greater<P2> > q;
  d[S][0] = 0;
  q.push(P2(0, P(S, 0)));
  long long ans = INF;

  while (!q.empty()) {
    int r = q.top().first,
        s = q.top().second.first, b = q.top().second.second;
    q.pop();
    if (d[s][b]+b > r) continue;

    for (P2 p : edges[s]) {
      int t = p.first;
      int r1 = p.second.first, r2 = p.second.second;
      int w = max(b, r2*2);
      if (d[t][w] > d[s][b] + r1) {
        d[t][w] = d[s][b] + r1;
        q.push(P2(d[t][w]+w, P(t, w)));

        if (t == D) ans = min(ans, d[D][w] + w);
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

Submission Info

Judge Result