Submission #364314

#	Time	Username	Problem	Language	Result	Execution time	Memory
364314		tushar_2658	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	260 ms	7904 KiB

ho_t4

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

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

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], rev[maxn];
ll dis[2][maxn];
int par[2][maxn];
vector<int> candidates;
int n, m;

void dijkstra(int id, int s){
  for(int i = 1; i <= n; ++i)dis[id][i] = -1;
  dis[id][s] = 0;
  using pii = pair<ll, int>;
  vector<bool> vis(n + 1);
  while(1){
    pii src = {inf, -1};
    for(int i = 1; i <= n; ++i){
      if(vis[i])continue;
      if(dis[id][i] < src.first && dis[id][i] != -1){
        src = {dis[id][i], i};
      }
    }
    if(src.first == inf)break;
    if(vis[src.second])continue;
    vis[src.second] = 1;
    for(auto i : edges[src.second]){
      ll cost = dis[id][src.second] + i.c;
      if(dis[id][i.x] > cost or dis[id][i.x] == -1){
        dis[id][i.x] = cost;
        par[id][i.x] = i.id;
      }
    }
  }
}

ll dis1[2][maxn];

void dijkstra1(int id, int s){
  for(int i = 1; i <= n; ++i)dis1[id][i] = -1;
  dis1[id][s] = 0;
  using pii = pair<ll, int>;
  vector<bool> vis(n + 1);
  while(1){
    pii src = {inf, -1};
    for(int i = 1; i <= n; ++i){
      if(vis[i])continue;
      if(dis1[id][i] < src.first && dis1[id][i] != -1){
        src = {dis1[id][i], i};
      }
    }
    if(src.first == inf)break;
    if(vis[src.second])continue;
    vis[src.second] = 1;
    for(auto i : g[src.second]){
      ll cost = dis1[id][src.second] + i.c;
      if(dis1[id][i.x] > cost or dis1[id][i.x] == -1){
        dis1[id][i.x] = cost;
      }
    }
  }
}

ll dis2[2][maxn];

void dijkstra2(int id, int s){
  for(int i = 1; i <= n; ++i)dis2[id][i] = -1;
  dis2[id][s] = 0;
  using pii = pair<ll, int>;
  vector<bool> vis(n + 1);
  while(1){
    pii src = {inf, -1};
    for(int i = 1; i <= n; ++i){
      if(vis[i])continue;
      if(dis2[id][i] < src.first && dis2[id][i] != -1){
        src = {dis2[id][i], i};
      }
    }
    if(src.first == inf)break;
    if(vis[src.second])continue;
    vis[src.second] = 1;
    for(auto i : rev[src.second]){
      ll cost = dis2[id][src.second] + i.c;
      if(dis2[id][i.x] > cost or dis2[id][i.x] == -1){
        dis2[id][i.x] = cost;
      }
    }
  }
}

ll ans = 1e18;

void 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);
  if(dis1[0][n] != -1 && dis1[1][1] != -1){
    ans = min(ans, D + dis1[0][n] + dis1[1][1]);
  }
}

int good[50005];

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

  cin >> n >> m;
  using pii = pair<ll, ll>;
  vector<pair<pii, pii>> inp;
  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));
    rev[v].push_back(E(u, C, D, i));
    inp.push_back({{u, v}, {C, D}});
  }
  memset(par, -1, sizeof par);
  dijkstra(0, 1);
  dijkstra(1, n);
  dijkstra2(0, 1);
  dijkstra2(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 = 1e18;
  if(dis[0][n] != -1 && dis[1][1] != -1)ans = dis[0][n] + dis[1][1];
  for(auto i : candidates){
    check(i);
    good[i] = 1;
  }
  for(int i = 0; i < m; ++i){
    if(!good[i]){
      ll x = 1e18, y = 1e18;
      if(dis[0][n] != -1)x = dis[0][n];
      if(dis[0][inp[i].first.second] != -1 && dis2[1][inp[i].first.first] != -1)x = min(x, dis[0][inp[i].first.second] + dis2[1][inp[i].first.first] + inp[i].second.first);
      if(dis[1][1] != -1)y = dis[1][1];
      if(dis[1][inp[i].first.second] != -1 && dis2[0][inp[i].first.first] != -1)y = min(y, dis[1][inp[i].first.second] + dis2[0][inp[i].first.first] + inp[i].second.first);
      ans = min(ans, x + y + inp[i].second.second);
    }
  }
  cout << (ans < inf ? ans : -1) << '\n';

  return 0;
}

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