제출 #156501

#제출 시각아이디문제언어결과실행 시간메모리
156501staniewzkiCommuter Pass (JOI18_commuter_pass)C++14
31 / 100
487 ms22224 KiB
#include<bits/stdc++.h> using namespace std; ostream& operator<<(ostream &out, string str) { for(char c : str) out << c; return out; } template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.first << ", " << p.second << ")"; } template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << "{"; for(auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << "}"; } void dump() { cerr << "\n"; } template<class T, class... Ts> void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #ifdef DEBUG # define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #else # define debug(...) false #endif #define REP(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define ST first #define ND second template<class T> int size(T && a) { return a.size(); } using LL = long long; using PII = pair<int, int>; vector<vector<PII>> graph; vector<LL> get_dist(int n, int s) { vector<LL> dist(n, 1e18); priority_queue<pair<LL, int>> Q; auto push = [&](int v, LL d) { dist[v] = d; Q.emplace(-dist[v], v); }; push(s, 0); while(!Q.empty()) { int v = Q.top().ND; Q.pop(); for(PII e : graph[v]) { if(dist[e.ST] > dist[v] + e.ND) push(e.ST, dist[v] + e.ND); } } return dist; } vector<LL> dist_u, dist_v, dist_s, dist_t; vector<bool> vis; LL dfs(int v, vector<LL> &d, LL min_u, LL min_v) { vis[v] = true; min_u = min(min_u, dist_u[v]); min_v = min(min_v, dist_v[v]); LL ret = min_u + min_v; for(PII e : graph[v]) if(d[v] == d[e.ST] + e.ND and not vis[e.ST]) ret = min(ret, dfs(e.ST, d, min_u, min_v)); debug(v, d, min_u, min_v); return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; int s, t, u, v; cin >> s >> t >> u >> v; s--, t--, u--, v--; graph.resize(n); REP(i, m) { int a, b, c; cin >> a >> b >> c; graph[a - 1].emplace_back(b - 1, c); graph[b - 1].emplace_back(a - 1, c); } dist_u = get_dist(n, u); dist_v = get_dist(n, v); dist_s = get_dist(n, s); dist_t = get_dist(n, t); debug(dist_s, dist_t); LL ans = dist_v[u]; vis.resize(n); REP(i, 2) { LL min_u = 1e18, min_v = 1e18; int x = (i ? s : t); auto &d = (i ? dist_t : dist_s); fill(vis.begin(), vis.end(), false); ans = min(ans, dfs(x, d, min_u, min_v)); } cout << ans << "\n"; }

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

commuter_pass.cpp: In function 'LL dfs(int, std::vector<long long int>&, LL, LL)':
commuter_pass.cpp:74:27: warning: statement has no effect [-Wunused-value]
  debug(v, d, min_u, min_v);
                           ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:101:23: warning: statement has no effect [-Wunused-value]
  debug(dist_s, dist_t);
                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...