Submission #364293

#	Time	Username	Problem	Language	Result	Execution time	Memory
364293		tushar_2658	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	186 ms	6108 KiB

ho_t4

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

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

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){
  for(int i = 1; i <= n; ++i)dis[id][i] = inf;
  dis[id][s] = 0;
  using pii = pair<ll, ll>;
  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();
    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){
        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){
  for(int i = 1; i <= n; ++i)dis1[id][i] = inf;
  dis1[id][s] = 0;
  using pii = pair<ll, ll>;
  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();
    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){
        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 good[50005];
ll dis2[maxn][maxn];

void floyd(){
  for(int k = 1; k <= n; ++k){
    for(int i = 1; i <= n; ++i){
      for(int j = 1; j <= n; ++j){
        if(dis2[i][k] + dis2[k][j] < dis2[i][j]){
          dis2[i][j] = dis2[i][k] + dis2[k][j];
        }
      }
    }
  }
}

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 < 2; ++i)for(int j = 1; j <= n; ++j)dis2[i][j] = inf;
  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));
    inp.push_back({{u, v}, {C, D}});
    dis2[u][v] = min(dis2[u][v], C);
  }
  memset(par, -1, sizeof par);
  dijkstra(0, 1);
  dijkstra(1, n);
  floyd();
  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));
    good[i] = 1;
  }
  for(int i = 0; i < m; ++i){
    if(!good[i]){
      ll x = inp[i].second.second + dis2[1][inp[i].first.second] + dis2[inp[i].first.first][n] + inp[i].second.first + dis[1][1];
      ll y = inp[i].second.second + dis2[n][inp[i].first.second] + dis2[1][inp[i].first.first] + inp[i].second.first + dis[0][n];
      ans = min(ans, min(x, y));
    }
  }
  cout << (ans > 1e16 ? -1 : ans) << '\n';

  return 0;
}

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