oj.uz

답안 #976912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
976912 2024-05-07T08:56:41 Z RedGrey1993 Commuter Pass (JOI18_commuter_pass) C++17
16 / 100
 267 ms 27436 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.resize(sz(edges_));
    fill(all(min_du), numeric_limits<T>::max());
    min_dv.resize(sz(edges_));
    fill(all(min_dv), numeric_limits<T>::max());
    distance_.resize(edges_.size());
    fill(distance_.begin(), distance_.end(), numeric_limits<T>::max());
    distance_[start] = 0;
    min_du[start] = du[start];
    min_dv[start] = dv[start];
    T ans = min_du[start] + min_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[e.to] = min(du[e.to], min_du[v]);
          min_dv[e.to] = min(dv[e.to], min_dv[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[e.to] = min(min_du[e.to], min_du[v]);
          min_dv[e.to] = min(min_dv[e.to], min_dv[v]);
          prev_vertex_[e.to].emplace_back(v);
        }
      }
    }

    vi vis(n, 0);
    queue<int> q;
    q.push(t);
    vis[t] = 1;
    ans = min(ans, min_du[t] + min_dv[t]);
    while (!q.empty()) {
      int tt = q.front(); q.pop();
      rep(i,0,sz(prev_vertex_[tt])) {
        int ss = prev_vertex_[tt][i];
        if (!vis[ss]) {
          vis[ss] = 1;
          ans = min(ans, min_du[ss] + min_dv[ss]);
          q.push(ss);
        }
      }
    }
    return ans;
  }

//  private:
  vector<vector<Edge>> &edges_;
  vector<T> distance_;
  vector<T> du,dv;
  vector<T> min_du,min_dv;
  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";
        }
        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:184:44:   required from here
commuter_pass.cpp:121: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]
  121 |       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:184: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 198 ms 27340 KB Output is correct
2 Correct 190 ms 26480 KB Output is correct
3 Correct 242 ms 26620 KB Output is correct
4 Correct 196 ms 26960 KB Output is correct
5 Correct 196 ms 26208 KB Output is correct
6 Correct 220 ms 27436 KB Output is correct
7 Correct 215 ms 26480 KB Output is correct
8 Correct 208 ms 26596 KB Output is correct
9 Correct 195 ms 27208 KB Output is correct
10 Correct 162 ms 27300 KB Output is correct
11 Correct 98 ms 19772 KB Output is correct
12 Correct 230 ms 27284 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 26760 KB Output is correct
2 Correct 267 ms 26544 KB Output is correct
3 Incorrect 222 ms 26564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2140 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 27340 KB Output is correct
2 Correct 190 ms 26480 KB Output is correct
3 Correct 242 ms 26620 KB Output is correct
4 Correct 196 ms 26960 KB Output is correct
5 Correct 196 ms 26208 KB Output is correct
6 Correct 220 ms 27436 KB Output is correct
7 Correct 215 ms 26480 KB Output is correct
8 Correct 208 ms 26596 KB Output is correct
9 Correct 195 ms 27208 KB Output is correct
10 Correct 162 ms 27300 KB Output is correct
11 Correct 98 ms 19772 KB Output is correct
12 Correct 230 ms 27284 KB Output is correct
13 Correct 238 ms 26760 KB Output is correct
14 Correct 267 ms 26544 KB Output is correct
15 Incorrect 222 ms 26564 KB Output isn't correct
16 Halted 0 ms 0 KB -