제출 #629663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629663		Abrar_Al_Samit	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	823 ms	5572 KiB

ho_t4

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

const int MX = 205;
const long long INF = 1e18;
const int MXM = 5e4 + 5;

struct Edge {
  int from, to, len, invert, id;
  bool vip;

  Edge() {vip = 0;}
  Edge(int _to, int _len, int _invert, int _id) {
    to = _to, len = _len, invert = _invert, id = _id;
    vip = 0;
  }
  Edge(int _from, int _to, int _len, int _invert, int _id) {
    from = _from, to = _to, len = _len, invert = _invert, id = _id;
    vip = 0;
  }
} List[MXM];

int n, m;
vector<vector<Edge>>g(MX, vector<Edge>()), gt(MX, vector<Edge>());
long long to_one[MX], to_n[MX], from_one[MX], from_n[MX];
int dad[MX];


void dijkstra(int sc, vector<vector<Edge>>&gr, long long *a) {
  for(int i=1; i<=n; ++i) {
    a[i] = INF;
  }

  a[sc] = 0;
  priority_queue<pair<long long,int>>pq;
  pq.emplace(0, sc);

  while(!pq.empty()) {
    int v; long long cost;
    tie(cost, v) = pq.top();
    pq.pop();
    cost = -cost;
    if(a[v]!=cost) continue;

    for(auto e : gr[v]) {
      if(cost+e.len<a[e.to]) {
        a[e.to] = cost+e.len;
        pq.emplace(-a[e.to], e.to);
        dad[e.to] = e.id;
      }
    }
  }
}
void dijkstra2(int sc, int ban, long long* a) {

  for(int i=1; i<=n; ++i) {
    a[i] = INF;
  }
  a[sc] = 0;
  priority_queue<pair<long long,int>>pq;
  pq.emplace(0, sc);

  while(!pq.empty()) {
    int v; long long cost;
    tie(cost, v) = pq.top();
    pq.pop();
    cost = -cost;
    if(a[v]!=cost) continue;

    for(auto e : g[v]) if(e.id!=ban) {
      if(cost+e.len<a[e.to]) {
        a[e.to] = cost+e.len;
        pq.emplace(-a[e.to], e.to);
      }
    }
  }
}
void PlayGround() {
  cin>>n>>m;
  for(int i=0; i<m; ++i) {
    int u, v, c, d;
    cin>>u>>v>>c>>d;
    g[u].emplace_back(Edge(v, c, d, i));
    gt[v].emplace_back(Edge(u, c, d, i));

    List[i] = {u, v, c, d, i};
  }

  dijkstra(1, g, from_one);

  int cur = n;
  while(cur!=1 && from_one[n]!=INF) {
    List[dad[cur]].vip = 1;
    cur = List[dad[cur]].from;
  }
  dijkstra(n, g, from_n);

  cur = 1;
  while(cur!=n && from_n[1]!=INF) {
    List[dad[cur]].vip = 1;
    cur = List[dad[cur]].from;
  }
  dijkstra(1, gt, to_one);
  dijkstra(n, gt, to_n);

  for(int i=1; i<=n; ++i) {
    for(auto &e : g[i]) {
      e = List[e.id];
    }
  }
  long long ans = INF;
  if(from_one[n]!=INF && from_n[1]!=INF) {
    ans = from_one[n] + from_n[1];
  }

  for(int u=1; u<=n; ++u) {
    for(auto e : g[u]) if(e.vip==false) {
      long long v, c, d;
      v = e.to, c = e.len, d = e.invert;

      //1->v->u->n->1
      if(from_one[v]!=INF && to_n[u]!=INF && from_n[1]!=INF) {
        ans = min(ans, from_one[v]+to_n[u]+from_n[1]+c+d);
      }
      //1->v->u->n->v->u->1
      if(from_one[v]!=INF && to_n[u]!=INF && from_n[v]!=INF && to_one[u]!=INF) {
        ans = min(ans, from_one[v]+c+to_n[u]+from_n[v]+c+to_one[u]+d);
      }

      //1->n->v->u->1
      if(from_one[n]!=INF && from_n[v]!=INF && to_one[u]!=INF) {
        ans = min(ans, from_one[n]+from_n[v]+to_one[u]+c+d);
      }
    }
  }

  for(int i=1; i<=n; ++i) {
    for(auto e : g[i]) if(e.vip) {
      dijkstra2(1, e.id, from_one);
      dijkstra2(n, e.id, from_n);

      long long u, v, c, d;
      u = e.from, v = e.to, c = e.len, d = e.invert;

      //1->v->u->n->1
      if(from_one[v]!=INF && to_n[u]!=INF && from_n[1]!=INF) {
        ans = min(ans, from_one[v]+to_n[u]+from_n[1]+c+d);
      }

      //1->v->u->n->v->u->1
      if(from_one[v]!=INF && to_n[u]!=INF && from_n[v]!=INF && to_one[u]!=INF) {
        ans = min(ans, from_one[v]+c+to_n[u]+from_n[v]+c+to_one[u]+d);
      }

      //1->n->v->u->1
      if(from_one[n]!=INF && from_n[v]!=INF && to_one[u]!=INF) {
        ans = min(ans, from_one[n]+from_n[v]+to_one[u]+c+d);
      }
    }
  }

  if(ans==INF) ans = -1;
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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