Submission #364280

#	Time	Username	Problem	Language	Result	Execution time	Memory
364280		tushar_2658	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	322 ms	3820 KiB

ho_t4

#include "bits/stdc++.h"
using namespace std;

const int maxn = 205;
using ll = long long;
ll inf = 1e18;

struct E {
  int x, id;
  ll c, d;
  E(int _x, ll _c, ll _d, int _id){
    x = _x, c = _c, d = _d;
    id = _id;
  }
  E(){}
};

vector<E> edges[maxn], g[maxn];
ll dis[2][maxn];
int par[2][maxn];
vector<int> candidates;
int n, m;

void dijkstra(int id, int s){
  memset(dis[id], 63, sizeof dis[id]);
  dis[id][s] = 0;
  using pii = pair<ll, int>;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  pq.push({0, s});
  vector<bool> vis(n + 1);
  while(!pq.empty()){
    pii src = pq.top();
    pq.pop();
    for(auto i : edges[src.second]){
      ll cost = dis[id][src.second] + i.c;
      if(dis[id][i.x] > cost){
        dis[id][i.x] = cost;
        par[id][i.x] = i.id;
        pq.push({cost, i.x});
      }
    }
  }
}

ll ans = inf;
ll dis1[2][maxn];

void dijkstra1(int id, int s){
  memset(dis1[id], 63, sizeof dis1[id]);
  dis1[id][s] = 0;
  using pii = pair<ll, int>;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  pq.push({0, s});
  vector<bool> vis(n + 1);
  while(!pq.empty()){
    pii src = pq.top();
    pq.pop();
    for(auto i : g[src.second]){
      ll cost = dis1[id][src.second] + i.c;
      if(dis1[id][i.x] > cost){
        dis1[id][i.x] = cost;
        pq.push({cost, i.x});
      }
    }
  }
}

ll check(int id){
  ll D = 0;
  for(int i = 1; i <= n; ++i)g[i].clear();
  for(int i = 1; i <= n; ++i){
    for(auto j : edges[i]){
      if(j.id != id){
        g[i].push_back(j);
      }else {
        g[j.x].push_back(E(i, j.c, j.d, j.id));
        D = j.d;
      }
    }
  }
  dijkstra1(0, 1);
  dijkstra1(1, n);
  return D + dis1[0][n] + dis1[1][1];
}

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < m; ++i){
    int u, v;
    ll C, D;
    cin >> u >> v >> C >> D;
    edges[u].push_back(E(v, C, D, i));
  }
  memset(par, -1, sizeof par);
  dijkstra(0, 1);
  dijkstra(1, n);
  for(int i = 0; i < 2; ++i){
    for(int j = 1; j <= n; ++j){
      if(par[i][j] != -1){
        candidates.push_back({par[i][j]});
      }
    }
  }
  sort(candidates.begin(), candidates.end());
  candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
  ans = min(ans, dis[0][n] + dis[1][1]);
  for(auto i : candidates){
    ans = min(ans, check(i));
  }
  cout << (ans > 1e18 ? -1 : ans) << '\n';

  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63