oj.uz

답안 #977107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977107 2024-05-07T11:46:44 Z RedGrey1993 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 313 ms 29104 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

// 函数名后面加 ll 就可以计算 long long类型对应的结果
// __builtin_ffs(x)
// 返回x中最后一个为1的位是从后向前的第几位
// __builtin_popcount(x)
// x中1的个数
// __builtin_ctz(x)
// x末尾0的个数。x=0时结果未定义。
// __builtin_clz(x)
// x前导0的个数。x=0时结果未定义。
// __builtin_parity(x)
// x中1的奇偶性。
#define highest_bit1_index(x) (31 - __builtin_clz(k))
#define highest_bit1_index_ll(x) (63 - __builtin_clzll(k))
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif


template <typename T>
class Dijkstra {
 public:
  struct Edge {
    int to;
    T cost;
    friend ostream &operator<<(ostream &os, const Edge &r) { return os << "<" << r.to << "," << r.cost << ">"; }
  };
  Dijkstra(vector<vector<Edge>> &edges) : edges_(edges) {}

  void ShortestPath(int start, vector<T>& d) {
    d.resize(edges_.size());
    fill(d.begin(), d.end(), numeric_limits<T>::max());
    d[start] = 0;
    // <min dis, vertex>
    using P = pair<T, int>;
    // make priority queue sort smaller integer first
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, start));

    while (!que.empty()) {
      P p = que.top();
      que.pop();
      int v = p.second;
      if (d[v] < p.first) continue;
      for (int i = 0; i < edges_[v].size(); ++i) {
        Edge e = edges_[v][i];
        if (d[e.to] > d[v] + e.cost) {
          d[e.to] = d[v] + e.cost;
          que.push(P(d[e.to], e.to));
        }
      }
    }
  }

  T ShortestPath(int start, int t, int u, int v) {
    ShortestPath(u, du);
    ShortestPath(v, dv);
    int n = sz(edges_);

    min_du_r.resize(n);
    fill(all(min_du_r), numeric_limits<T>::max());
    min_dv_r.resize(n);
    fill(all(min_dv_r), numeric_limits<T>::max());
    distance_.resize(n);
    fill(distance_.begin(), distance_.end(), numeric_limits<T>::max());
    distance_[t] = 0;
    min_du_r[t] = du[t];
    min_dv_r[t] = dv[t];
    // <min dis, vertex>
    using P = pair<T, int>;
    // make priority queue sort smaller integer first
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, t));

    while (!que.empty()) {
      P p = que.top();
      que.pop();
      int v = p.second;
      if (distance_[v] < p.first) continue;
      for (int i = 0; i < edges_[v].size(); ++i) {
        Edge e = edges_[v][i];
        if (distance_[e.to] > distance_[v] + e.cost) {
          distance_[e.to] = distance_[v] + e.cost;
          min_du_r[e.to] = min(du[e.to], min_du_r[v]);
          min_dv_r[e.to] = min(dv[e.to], min_dv_r[v]);

          que.push(P(distance_[e.to], e.to));
        } else if (distance_[e.to] == distance_[v] + e.cost) {
          min_du_r[e.to] = min(min_du_r[e.to], min_du_r[v]);
          min_dv_r[e.to] = min(min_dv_r[e.to], min_dv_r[v]);
        }
      }
    }

    min_du_l.resize(sz(edges_));
    fill(all(min_du_l), numeric_limits<T>::max());
    min_dv_l.resize(sz(edges_));
    fill(all(min_dv_l), numeric_limits<T>::max());
    distance_.resize(edges_.size());
    fill(distance_.begin(), distance_.end(), numeric_limits<T>::max());
    distance_[start] = 0;
    min_du_l[start] = du[start];
    min_dv_l[start] = dv[start];
    prev_vertex_.resize(n);
    rep(i,0,sz(prev_vertex_)) prev_vertex_[i].clear();
    // // <min dis, vertex>
    // using P = pair<T, int>;
    // // make priority queue sort smaller integer first
    // priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, start));

    while (!que.empty()) {
      P p = que.top();
      que.pop();
      int v = p.second;
      if (distance_[v] < p.first) continue;
      for (int i = 0; i < edges_[v].size(); ++i) {
        Edge e = edges_[v][i];
        if (distance_[e.to] > distance_[v] + e.cost) {
          distance_[e.to] = distance_[v] + e.cost;
          min_du_l[e.to] = min(du[e.to], min_du_l[v]);
          min_dv_l[e.to] = min(dv[e.to], min_dv_l[v]);

          prev_vertex_[e.to] = {v};
          que.push(P(distance_[e.to], e.to));
        } else if (distance_[e.to] == distance_[v] + e.cost) {
          min_du_l[e.to] = min(min_du_l[e.to], min_du_l[v]);
          min_dv_l[e.to] = min(min_dv_l[e.to], min_dv_l[v]);
          prev_vertex_[e.to].emplace_back(v);
        }
      }
    }

    vi vis(n, 0);
    queue<int> q;
    q.push(t);
    vis[t] = 1;
    T ans = min(min_du_l[t] + min_dv_r[t], min_du_r[t] + min_dv_l[t]);
    // dbg(ans);
    while (!q.empty()) {
      int tt = q.front(); q.pop();
      // dbg(tt);
      rep(i,0,sz(prev_vertex_[tt])) {
        int ss = prev_vertex_[tt][i];
        if (!vis[ss]) {
          vis[ss] = 1;
          T mm = min(min_du_l[ss] + min_dv_r[ss], min_du_r[ss] + min_dv_l[ss]);
          ans = min(ans, mm);
          q.push(ss);
        }
      }
    }
    return min(ans, du[v]);
  }

//  private:
  vector<vector<Edge>> &edges_;
  vector<T> distance_;
  vector<T> du,dv;
  vector<T> min_du_l,min_dv_l;
  vector<T> min_du_r,min_dv_r;
  vector<vi> prev_vertex_;  // for path restore
};
using DijkstraT = Dijkstra<long long>;
using Edge = DijkstraT::Edge;

class Solution {
public:
    void Solve() {
        int n,m;
        while(cin>>n>>m) {
            int s,t,u,v;
            cin>>s>>t>>u>>v;
            s--;t--;u--;v--;
            int a,b,c;
            vector<vector<Edge>> edges(n);
            rep(i,0,m) {
              cin>>a>>b>>c;
              a--; b--;
              edges[a].emplace_back(Edge{b,c});
              edges[b].emplace_back(Edge{a,c});
            }
            DijkstraT dj(edges);
            cout << dj.ShortestPath(s,t,u,v) << "\n";
            // break;
        }
        cout.flush();
    }
private:
};

// # define FILE_IO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
    set_io("input");
    Solution().Solve();

    return 0;
}

Compilation message

commuter_pass.cpp: In instantiation of 'T Dijkstra<T>::ShortestPath(int, int, int, int) [with T = long long int]':
commuter_pass.cpp:222:44:   required from here
commuter_pass.cpp:118:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Dijkstra<long long int>::Edge, std::allocator<Dijkstra<long long int>::Edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |       for (int i = 0; i < edges_[v].size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:155:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Dijkstra<long long int>::Edge, std::allocator<Dijkstra<long long int>::Edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |       for (int i = 0; i < edges_[v].size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In instantiation of 'void Dijkstra<T>::ShortestPath(int, std::vector<_Tp>&) [with T = long long int]':
commuter_pass.cpp:94:17:   required from 'T Dijkstra<T>::ShortestPath(int, int, int, int) [with T = long long int]'
commuter_pass.cpp:222:44:   required from here
commuter_pass.cpp:83:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Dijkstra<long long int>::Edge, std::allocator<Dijkstra<long long int>::Edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |       for (int i = 0; i < edges_[v].size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 28620 KB Output is correct
2 Correct 310 ms 28136 KB Output is correct
3 Correct 255 ms 28508 KB Output is correct
4 Correct 235 ms 28168 KB Output is correct
5 Correct 248 ms 27956 KB Output is correct
6 Correct 244 ms 28624 KB Output is correct
7 Correct 234 ms 28040 KB Output is correct
8 Correct 262 ms 28104 KB Output is correct
9 Correct 251 ms 28688 KB Output is correct
10 Correct 203 ms 28728 KB Output is correct
11 Correct 82 ms 21076 KB Output is correct
12 Correct 258 ms 28932 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 28280 KB Output is correct
2 Correct 313 ms 28096 KB Output is correct
3 Correct 255 ms 27988 KB Output is correct
4 Correct 270 ms 27920 KB Output is correct
5 Correct 273 ms 28040 KB Output is correct
6 Correct 261 ms 28368 KB Output is correct
7 Correct 286 ms 28016 KB Output is correct
8 Correct 280 ms 28156 KB Output is correct
9 Correct 285 ms 28128 KB Output is correct
10 Correct 272 ms 27928 KB Output is correct
11 Correct 96 ms 20968 KB Output is correct
12 Correct 259 ms 28420 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2136 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 12 ms 3852 KB Output is correct
5 Correct 6 ms 2140 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 732 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 6 ms 2056 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 544 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 28620 KB Output is correct
2 Correct 310 ms 28136 KB Output is correct
3 Correct 255 ms 28508 KB Output is correct
4 Correct 235 ms 28168 KB Output is correct
5 Correct 248 ms 27956 KB Output is correct
6 Correct 244 ms 28624 KB Output is correct
7 Correct 234 ms 28040 KB Output is correct
8 Correct 262 ms 28104 KB Output is correct
9 Correct 251 ms 28688 KB Output is correct
10 Correct 203 ms 28728 KB Output is correct
11 Correct 82 ms 21076 KB Output is correct
12 Correct 258 ms 28932 KB Output is correct
13 Correct 274 ms 28280 KB Output is correct
14 Correct 313 ms 28096 KB Output is correct
15 Correct 255 ms 27988 KB Output is correct
16 Correct 270 ms 27920 KB Output is correct
17 Correct 273 ms 28040 KB Output is correct
18 Correct 261 ms 28368 KB Output is correct
19 Correct 286 ms 28016 KB Output is correct
20 Correct 280 ms 28156 KB Output is correct
21 Correct 285 ms 28128 KB Output is correct
22 Correct 272 ms 27928 KB Output is correct
23 Correct 96 ms 20968 KB Output is correct
24 Correct 259 ms 28420 KB Output is correct
25 Correct 7 ms 2136 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 12 ms 3852 KB Output is correct
29 Correct 6 ms 2140 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 2 ms 732 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 6 ms 2056 KB Output is correct
35 Correct 1 ms 716 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 544 KB Output is correct
40 Correct 236 ms 28816 KB Output is correct
41 Correct 255 ms 29104 KB Output is correct
42 Correct 250 ms 28764 KB Output is correct
43 Correct 98 ms 21160 KB Output is correct
44 Correct 85 ms 21076 KB Output is correct
45 Correct 238 ms 27860 KB Output is correct
46 Correct 252 ms 27684 KB Output is correct
47 Correct 239 ms 28476 KB Output is correct
48 Correct 98 ms 20628 KB Output is correct
49 Correct 196 ms 28496 KB Output is correct
50 Correct 221 ms 27828 KB Output is correct
51 Correct 231 ms 27676 KB Output is correct