Submission #1139045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139045		bozocode	Commuter Pass (JOI18_commuter_pass)	C++20	Compilation error	0 ms	0 KiB

commuter_pass

#include <bits/stdc++.h>
#define vec vector
#define long int64_t
using namespace std;

int N, S, T;
vec<vec<array<int, 2>>> rails;
vec<long> cost, ucost, vcost;

bool cmp (int u, int v) {
    return cost[u] < cost[v];
};

void dijkstra(int source) {
    cost.clear(); cost.resize(N, 1e18);
	cost[source] = 0;
    set<int, decltype(cmp)> s(cmp);
	s.insert(source);
	while (!s.empty()) {
		int u = *s.begin();
		s.erase(s.begin());
		for (auto [v, c] : rails[u]) {
			if (c + cost[u] < cost[v]) {
				s.erase(v);
				cost[v] = c + cost[u];
				s.insert(v);
			}
		}
	}
}

long dpdijkstra(bool change) {
    if (change) { swap(S, T); }
    vec<long> uclose(N, 1e18), vclose(N, 1e18);
    for (int i = 0; i < N; i++) {
        uclose[i] = ucost[i];
        vclose[i] = vcost[i];
    }
	cost.clear(); cost.resize(N, 1e18);
	cost[S] = 0;
    multiset<int, decltype(cmp)> s(cmp);
	s.insert(S);
	while (!s.empty()) {
		int u = *s.begin();
		s.erase(s.begin());
		for (auto [v, c] : rails[u]) {
            if (c + cost[u] > cost[v]) { continue; }
            //okay what tf happened
            //why does it just become min min and its fine
            //
            //if its the first time we can put on both
            //if its the second time onwards we have to be more careful
            //holy crap graph dp is tough, be careful!
			if (c + cost[u] < cost[v]) {
				s.erase(v);
				cost[v] = c + cost[u];
				uclose[v] = min(ucost[v], uclose[u]);
				vclose[v] = min(vcost[v], vclose[u]);
				s.insert(v);
			}
			if (min(ucost[v], uclose[u]) + min(vcost[v], vclose[u]) < uclose[v] + vclose[v]) {
				uclose[v] = min(ucost[v], uclose[u]);
				vclose[v] = min(vcost[v], vclose[u]);
			}
		}
	}
    return uclose[T] + vclose[T];
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	int M; cin >> N >> M;
	cin >> S >> T; S--; T--;
	int U, V; cin >> U >> V; U--; V--;
	rails.resize(N);
	for (int i = 0; i < M; i++) {
		int u, v, c; cin >> u >> v >> c; u--; v--;
		rails[u].push_back({v, c});
		rails[v].push_back({u, c});
	}
    dijkstra(U);
	ucost = cost; 
    dijkstra(V);
    vcost = cost;
    long ans = ucost[V];
    ans = min(ans, dpdijkstra(false));
    ans = min(ans, dpdijkstra(true));
    cout << ans << endl;
}

Compilation message (stderr)

In file included from /usr/include/c++/11/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:81,
                 from commuter_pass.cpp:1:
/usr/include/c++/11/bits/stl_tree.h: In instantiation of 'struct std::_Rb_tree_key_compare<bool(int, int)>':
/usr/include/c++/11/bits/stl_tree.h:660:9:   required from 'struct std::_Rb_tree<int, int, std::_Identity<int>, bool(int, int), std::allocator<int> >::_Rb_tree_impl<bool(int, int), false>'
/usr/include/c++/11/bits/stl_tree.h:706:31:   required from 'class std::_Rb_tree<int, int, std::_Identity<int>, bool(int, int), std::allocator<int> >'
/usr/include/c++/11/bits/stl_set.h:133:17:   required from 'class std::set<int, bool(int, int)>'
commuter_pass.cpp:17:34:   required from here
/usr/include/c++/11/bits/stl_tree.h:144:33: error: data member 'std::_Rb_tree_key_compare<bool(int, int)>::_M_key_compare' invalidly declared function type
  144 |       _Key_compare              _M_key_compare;
      |                                 ^~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_tree.h: In instantiation of 'class std::_Rb_tree<int, int, std::_Identity<int>, bool(int, int), std::allocator<int> >':
/usr/include/c++/11/bits/stl_set.h:133:17:   required from 'class std::set<int, bool(int, int)>'
commuter_pass.cpp:17:34:   required from here
/usr/include/c++/11/bits/stl_tree.h:991:7: error: function returning a function
  991 |       key_comp() const
      |       ^~~~~~~~
In file included from /usr/include/c++/11/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:87,
                 from commuter_pass.cpp:1:
/usr/include/c++/11/bits/stl_set.h: In instantiation of 'class std::set<int, bool(int, int)>':
commuter_pass.cpp:17:34:   required from here
/usr/include/c++/11/bits/stl_set.h:327:7: error: function returning a function
  327 |       key_comp() const
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_set.h:331:7: error: function returning a function
  331 |       value_comp() const
      |       ^~~~~~~~~~
In file included from /usr/include/c++/11/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:87,
                 from commuter_pass.cpp:1:
/usr/include/c++/11/bits/stl_multiset.h: In instantiation of 'class std::multiset<int, bool(int, int)>':
commuter_pass.cpp:41:39:   required from here
/usr/include/c++/11/bits/stl_multiset.h:323:7: error: function returning a function
  323 |       key_comp() const
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_multiset.h:327:7: error: function returning a function
  327 |       value_comp() const
      |       ^~~~~~~~~~