제출 #629310

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

ho_t4

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

const int MX = 205;
const int INF = 2e9+10;

struct Edge {
  int to, len, invert;

  Edge() {}
  Edge(int _to, int _len, int _invert) {
    to = _to, len = _len, invert = _invert;
  }
};

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


void dijkstra(int sc, vector<vector<Edge>>&gr, int *a) {
  a[sc] = 0;
  priority_queue<pair<int,int>>pq;
  pq.emplace(0, sc);

  while(!pq.empty()) {
    int v, 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);
      }
    }
  }
}
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));
    gt[v].emplace_back(Edge(u, c, d));
  }

  for(int i=1; i<=n; ++i) {
    to_one[i] = to_n[i] = from_one[i] = from_n[i] = edge_case[i] = edge_case2[i] = INF;
  }

  dijkstra(1, g, from_one);
  dijkstra(n, g, from_n);
  dijkstra(1, gt, to_one);
  dijkstra(n, gt, to_n);


  int 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]) {
      int v, c, d;
      v = e.to, c = e.len, d = e.invert;

      if(u==1 && v==n) {
        continue;
      }
      if(u==n && v==1) {
        continue;
      }

      //1->v->u->n->1
      if(u!=1 && v!=n && 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->n->v->u->1
      if(v!=1 && u!=n && 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);
      }
    }
  }

  {
    vector<pair<int,int>>one_to_n;
    for(auto e : g[1]) if(e.to==n) {
      one_to_n.emplace_back(e.len, e.invert);
    }
    int sz = one_to_n.size();
    if(sz==0) goto outside;
    for(int i=0; i<g[1].size(); ++i) if(g[1][i].to==n) {
      swap(g[1][i], g[1].back());
      g[1].pop_back();
      --i;
    }
    dijkstra(1, g, edge_case);
    int pre[sz], suf[sz];
    pre[0] = one_to_n[0].first;
    for(int i=1; i<sz; ++i) {
      pre[i] = min(pre[i-1], one_to_n[i].first);
    }
    suf[sz-1] = one_to_n[sz-1].first;
    for(int i=sz-2; i>-1; --i) {
      suf[i] = min(suf[i+1], one_to_n[i].first);
    }

    for(int i=0; i<sz; ++i) {
      int dist = edge_case[n];
      if(i) dist = min(dist, pre[i-1]);
      if(i<sz-1) dist = min(dist, suf[i+1]);

      if(dist==INF) continue;
      ans = min(ans, dist+one_to_n[i].first+one_to_n[i].second);
    }

    for(int i=0; i<sz; ++i) {
      g[1].emplace_back(Edge(n, one_to_n[i].first, one_to_n[i].second));
    }
  }
  outside:
  {
    vector<pair<int,int>>n_to_one;
    for(auto e : g[n]) if(e.to==1) {
      n_to_one.emplace_back(e.len, e.invert);
    }
    int sz = n_to_one.size();
    if(sz==0) goto outside2;
    for(int i=0; i<g[n].size(); ++i) if(g[n][i].to==1) {
      swap(g[n][i], g[n].back());
      g[n].pop_back();
      --i;
    }
    dijkstra(n, g, edge_case2);
    int pre[sz], suf[sz];
    pre[0] = n_to_one[0].first;
    for(int i=1; i<sz; ++i) {
      pre[i] = min(pre[i-1], n_to_one[i].first);
    }
    suf[sz-1] = n_to_one[sz-1].first;
    for(int i=sz-2; i>-1; --i) {
      suf[i] = min(suf[i+1], n_to_one[i].first);
    }

    for(int i=0; i<sz; ++i) {
      int dist = edge_case2[1];
      if(i) dist = min(dist, pre[i-1]);
      if(i<sz-1) dist = min(dist, suf[i+1]);
      if(dist==INF) continue;
      ans = min(ans, dist+n_to_one[i].first+n_to_one[i].second);
    }

    //no need to revert the changes in g
  }
  outside2:

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

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'void PlayGround()':
ho_t4.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0; i<g[1].size(); ++i) if(g[1][i].to==n) {
      |                  ~^~~~~~~~~~~~
ho_t4.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int i=0; i<g[n].size(); ++i) if(g[n][i].to==1) {
      |                  ~^~~~~~~~~~~~

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