제출 #407566

#제출 시각아이디문제언어결과실행 시간메모리
407566LittleFlowers__Commuter Pass (JOI18_commuter_pass)C++17
0 / 100
1444 ms20144 KiB
/*input 6 6 1 6 1 4 1 2 1 2 3 1 3 5 1 2 4 3 4 5 2 5 6 1 */ #include <bits/stdc++.h> using namespace std; int n, m, s, t, u, v; vector<pair<int, int>> ad[100010]; void dij(int fw, vector<long long>&f) { fill(f.begin(), f.end(), 1e15); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; q.push({0, fw}); f[fw] = 0; while (q.size()) { int w, u; tie(w, u) = q.top(); q.pop(); for (auto v : ad[u]) { if (f[v.first] > w + v.second) { f[v.first] = w + v.second; q.push({w + v.second, v.first}); } } } } main() { cin >> n >> m >> s >> t >> u >> v; for (int i = 0; i < m; ++i) { int x, y, w; cin >> x >> y >> w; ad[x].push_back({y, w}); ad[y].push_back({x, w}); } vector<long long> fs(n + 1), ft(n + 1), fu(n + 1), fv(n + 1); dij(t, ft); dij(u, fu); dij(v, fv); dij(s, fs); long long ret = fu[v]; vector<long long> f(n + 1, 1e15), pf(n + 1, 1e15); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; q.push({0, s}); f[s] = 0; pf[s] = fu[s]; while (q.size()) { long long w; int u; tie(w, u) = q.top(); q.pop(); ret = min(ret, pf[u] + fv[u]); for (auto v : ad[u]) { if (fs[v.first] + ft[v.first] == fs[t]) { pf[v.first] = min({pf[v.first], fu[v.first], pf[u]}); if (f[v.first] > w + v.second) { f[v.first] = w + v.second; q.push({w + v.second, v.first}); } } } } cout << ret; }

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

commuter_pass.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...