Submission #618728

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

typedef pair<long long, int> PLI;

struct edge {
  int to;
  int cost;
  int dst;
  long long penalty;
};

const long long INF = 1LL<<32;
int n, m, src, dst;
vector<edge> es[25252];
long long dist[25252];
long long dist2[25252];

bool check(long long x) {
  priority_queue<PLI, vector<PLI>, greater<PLI> > Q;
  fill(dist, dist + n, INF);
  dist[src] = 0;
  Q.push(MP(0, src));

  while (!Q.empty()) {
    long long cost = Q.top().first;
    int v = Q.top().second;
    Q.pop();

    if (cost > dist[v])
      continue;

    REP (i, es[v].size()) {
      edge &e = es[v][i];
      if (cost + e.penalty + dist2[e.dst] > x)
        continue;
      if (cost + e.cost < dist[e.to]) {
        dist[e.to] = cost + e.cost;
        Q.push(MP(dist[e.to], e.to));
      }
    }
  }
  return dist[dst] <= x;
}

int main() {
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> src >> dst;
    REP (i, m) {
      int l;
      cin >> l;

      vector<int> s(l), w(l);
      REP (i, l) cin >> s[i];
      REP (i, l-1) cin >> w[i];

      // forward
      long long penalty = accumulate(ALL(w), 0LL);
      REP (i, l-1) {
        es[s[i]].push_back({s[i+1], w[i], s.back(), penalty});
        penalty -= w[i];
      }

      // backword
      penalty = accumulate(ALL(w), 0LL);
      for (int i = l-1; i > 0; i--) {
        es[s[i]].push_back({s[i-1], w[i-1], s.front(), penalty});
        penalty -= w[i-1];
      }
    }

    // dijkstra to dst
    priority_queue<PLI, vector<PLI>, greater<PLI> > Q;
    fill(dist2, dist2+n, INF);
    dist2[dst] = 0;
    Q.push(MP(0 ,dst));

    while (!Q.empty()) {
      long long cost = Q.top().first;
      int v = Q.top().second;
      Q.pop();

      if (dist2[v] != cost)
        continue;

      REP (i, es[v].size()) {
        int w = es[v][i].to;
        int c = es[v][i].cost;

        if (cost + c < dist2[w]) {
          dist2[w] = cost + c;
          Q.push(MP(dist2[w], w));
        }
      }
    }

    // dijkstra from src with binary-search check
    long long hi = 1LL<<32;
    long long lo = -1;

    while (hi - lo > 1) {
      long long mi = (hi + lo) >> 1;
      if (check(mi))
        hi = mi;
      else
        lo = mi;
    }
    
    cout << hi << endl;
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:85:28: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         es[s[i]].push_back({s[i+1], w[i], s.back(), penalty});
                            ^
./Main.cpp:85:61: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         es[s[i]].push_back({s[i+1], w[i], s.back(), penalty});
                                                             ^
./Main.cpp:92:28: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         es[s[i]].push_back({s[i-1], w[i-1], s.front(), penalty});
                            ^
./Main.cpp:92:64: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
         es[s[i]].push_back({s[i-1], w[i-1], s.front(), penalty});
                                                                ^

Judge Result