제출 #939781

#제출 시각아이디문제언어결과실행 시간메모리
939781mansurCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
371 ms82444 KiB
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #include<bits/stdc++.h> using namespace std; #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define sz(a) (int)a.size() #define s second #define f first using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; const int N = 1e6 + 1, mod = 1e9 + 7; const ll inf = 1e18; double eps = 1e-15; bool flg = 0; vector<pll> g[N]; ll d[4][N]; void djk(int x, int tp) { set<pll> s; d[tp][x] = 0; s.insert({0, x}); while (sz(s)) { x = (*s.begin()).s; s.erase(s.begin()); for (auto [to, w]: g[x]) { if (d[tp][to] <= d[tp][x] + w) continue; s.erase({d[tp][to], to}); d[tp][to] = d[tp][x] + w; s.insert({d[tp][to], to}); } } } vector<int> gr[N], was(N), ord; void dfs(int u) { was[u] = 1; for (int to: gr[u]) { if (!was[to]) dfs(to); } ord.push_back(u); } void slv() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 0; j < 4; j++) d[j][i] = inf; } int s, t; cin >> s >> t; int u, v; cin >> u >> v; int a[m + 1], b[m + 1], c[m + 1]; for (int i = 1; i <= m; i++) { cin >> a[i] >> b[i] >> c[i]; g[a[i]].push_back({b[i], c[i]}); g[b[i]].push_back({a[i], c[i]}); } djk(s, 0); djk(t, 1); djk(u, 2); djk(v, 3); ll L = d[0][t]; for (int i = 1; i <= m; i++) { if (d[0][a[i]] + d[1][b[i]] + c[i] == L) { //cout << a[i] << ' ' << b[i] << '\n'; gr[b[i]].push_back(a[i]); } if (d[0][b[i]] + d[1][a[i]] + c[i] == L) { //cout << b[i] << ' ' << a[i] << '\n'; gr[a[i]].push_back(b[i]); } } for (int i = 1; i <= n; i++) { if (sz(gr[i]) && !was[i]) dfs(i); } //cout << '\n'; vector<ll> dp1(n + 1, inf), dp2(n + 1, inf); ll ans = d[2][v]; for (int x: ord) { dp1[x] = d[2][x]; dp2[x] = d[3][x]; for (int to: gr[x]) { dp1[x] = min(dp1[x], dp1[to]); dp2[x] = min(dp2[x], dp2[to]); } //cout << x << ' ' << dp1[x] << ' ' << dp2[x] << '\n'; ans = min(ans, d[3][x] + dp1[x]); ans = min(ans, d[2][x] + dp2[x]); } cout << ans; } main() { //freopen("rsq.in", "r", stdin); //freopen("rsq.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int tp = 1; if (flg) cin >> tp; while (tp--) { //cout << "Case #" << cur++ << ": "; slv(); } } //wenomechainsama

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

commuter_pass.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | 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...