Submission #530711

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
530711	2022-02-26T14:11:37 Z	Bungmint	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	346 ms	20224 KB

commuter_pass

//Copyright © 2021 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define REP(a) F0R(_, a)

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const ld PI = acos((ld)-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out()
{
    cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda{
	template <typename Fun>
	struct y_combinator_result{
		Fun fun_;
		template <typename T> 
		explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)){}
		template <typename...Args>
		decltype(auto) operator()(Args &&...args){
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun){
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

void setIO(string s) // USACO
{
	#ifndef LOCAL
	    freopen((s + ".in").c_str(), "r", stdin);
	    freopen((s + ".out").c_str(), "w", stdout);
	#endif
}

const int N = 1e5 + 10;
vpi g[N];
ll distUV[2][N];
ll dist[N], mi[2][N];


void dijkstra(int src, int fl) {
	pqg<pll> pq;
	fill(distUV[fl], distUV[fl] + N, LINF);
	distUV[fl][src] = 0;
	pq.push({0, src});
	while (sz(pq)) {
		auto [d, u] = pq.top();
		pq.pop();
		dbg(distUV[fl][u], fl, u);
		if (distUV[fl][u] < d) continue;
		for (auto &[v, w] : g[u]) {
			if (ckmin(distUV[fl][v], distUV[fl][u] + w)) {
				pq.push({distUV[fl][v], v});
			}
		}
	}
}


ll modDijkstra(int src, int dest) {
	pqg<pll> pq;
	fill(dist, dist + N, LINF);
	F0R(i, 2) fill(mi[i], mi[i] + N, LINF);
	pq.push({0, src});
	dist[src] = 0;
	mi[0][src] = distUV[0][src];
	mi[1][src] = distUV[1][src];
	dbg(distUV[1][src]);
	while (sz(pq)) {
		auto [d, u] = pq.top();
		pq.pop();
		if (dist[u] < d) continue;
		for (auto &[v, w] : g[u]) {
			if (ckmin(dist[v], dist[u] + w)) {
				pq.push({dist[v], v});
				mi[0][v] = min(mi[0][u], distUV[0][v]);
				mi[1][v] = min(mi[1][u], distUV[1][v]);
			}else if (dist[v] == dist[u] + w) {
				if (mi[0][v] + mi[1][v] >= min(mi[0][u], distUV[0][v]) + min(mi[1][u], distUV[1][v])) {
					mi[0][v] = min(mi[0][u], distUV[0][v]);
					mi[1][v] = min(mi[1][u], distUV[1][v]);
				}
			}
		}
	}
	return mi[0][dest] + mi[1][dest];
}


void solve()
{
	int n, m, u, v, s, t;
	cin >> n >> m;
	cin >> s >> t >> u >> v;
	s--, t--, u--, v--;
	REP(m) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	dijkstra(u, 0);
	dijkstra(v, 1);
	cout << min({modDijkstra(s, t), modDijkstra(t, s), distUV[0][v]}) << "\n";
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int testcase=1;
    // cin >> testcase;
    while (testcase--)
    {
        solve();
    }
}

Compilation message

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:71:18: warning: statement has no effect [-Wunused-value]
   71 | #define dbg(...) 42
      |                  ^~
commuter_pass.cpp:113:3: note: in expansion of macro 'dbg'
  113 |   dbg(distUV[fl][u], fl, u);
      |   ^~~
commuter_pass.cpp: In function 'll modDijkstra(int, int)':
commuter_pass.cpp:71:18: warning: statement has no effect [-Wunused-value]
   71 | #define dbg(...) 42
      |                  ^~
commuter_pass.cpp:132:2: note: in expansion of macro 'dbg'
  132 |  dbg(distUV[1][src]);
      |  ^~~
commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |      freopen((s + ".in").c_str(), "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:95:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      freopen((s + ".out").c_str(), "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	17380 KB	Output is correct
2	Correct	295 ms	16144 KB	Output is correct
3	Correct	318 ms	17180 KB	Output is correct
4	Correct	262 ms	16260 KB	Output is correct
5	Correct	279 ms	15924 KB	Output is correct
6	Correct	269 ms	17320 KB	Output is correct
7	Correct	259 ms	15960 KB	Output is correct
8	Correct	296 ms	15968 KB	Output is correct
9	Correct	272 ms	15832 KB	Output is correct
10	Correct	241 ms	15836 KB	Output is correct
11	Correct	100 ms	10952 KB	Output is correct
12	Correct	331 ms	15880 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	293 ms	16160 KB	Output is correct
2	Correct	312 ms	15956 KB	Output is correct
3	Correct	317 ms	15956 KB	Output is correct
4	Correct	311 ms	15964 KB	Output is correct
5	Correct	346 ms	16112 KB	Output is correct
6	Correct	328 ms	16008 KB	Output is correct
7	Correct	327 ms	15968 KB	Output is correct
8	Correct	295 ms	15924 KB	Output is correct
9	Correct	337 ms	15972 KB	Output is correct
10	Correct	293 ms	16000 KB	Output is correct
11	Correct	111 ms	10916 KB	Output is correct
12	Correct	322 ms	16208 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	7672 KB	Output is correct
2	Correct	4 ms	6604 KB	Output is correct
3	Correct	4 ms	6604 KB	Output is correct
4	Correct	17 ms	8596 KB	Output is correct
5	Correct	11 ms	7628 KB	Output is correct
6	Correct	4 ms	6656 KB	Output is correct
7	Correct	5 ms	6648 KB	Output is correct
8	Correct	6 ms	6724 KB	Output is correct
9	Correct	4 ms	6604 KB	Output is correct
10	Correct	10 ms	7628 KB	Output is correct
11	Correct	4 ms	6592 KB	Output is correct
12	Correct	3 ms	6604 KB	Output is correct
13	Correct	4 ms	6604 KB	Output is correct
14	Correct	4 ms	6604 KB	Output is correct
15	Correct	4 ms	6520 KB	Output is correct

Subtask #4

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	17380 KB	Output is correct
2	Correct	295 ms	16144 KB	Output is correct
3	Correct	318 ms	17180 KB	Output is correct
4	Correct	262 ms	16260 KB	Output is correct
5	Correct	279 ms	15924 KB	Output is correct
6	Correct	269 ms	17320 KB	Output is correct
7	Correct	259 ms	15960 KB	Output is correct
8	Correct	296 ms	15968 KB	Output is correct
9	Correct	272 ms	15832 KB	Output is correct
10	Correct	241 ms	15836 KB	Output is correct
11	Correct	100 ms	10952 KB	Output is correct
12	Correct	331 ms	15880 KB	Output is correct
13	Correct	293 ms	16160 KB	Output is correct
14	Correct	312 ms	15956 KB	Output is correct
15	Correct	317 ms	15956 KB	Output is correct
16	Correct	311 ms	15964 KB	Output is correct
17	Correct	346 ms	16112 KB	Output is correct
18	Correct	328 ms	16008 KB	Output is correct
19	Correct	327 ms	15968 KB	Output is correct
20	Correct	295 ms	15924 KB	Output is correct
21	Correct	337 ms	15972 KB	Output is correct
22	Correct	293 ms	16000 KB	Output is correct
23	Correct	111 ms	10916 KB	Output is correct
24	Correct	322 ms	16208 KB	Output is correct
25	Correct	10 ms	7672 KB	Output is correct
26	Correct	4 ms	6604 KB	Output is correct
27	Correct	4 ms	6604 KB	Output is correct
28	Correct	17 ms	8596 KB	Output is correct
29	Correct	11 ms	7628 KB	Output is correct
30	Correct	4 ms	6656 KB	Output is correct
31	Correct	5 ms	6648 KB	Output is correct
32	Correct	6 ms	6724 KB	Output is correct
33	Correct	4 ms	6604 KB	Output is correct
34	Correct	10 ms	7628 KB	Output is correct
35	Correct	4 ms	6592 KB	Output is correct
36	Correct	3 ms	6604 KB	Output is correct
37	Correct	4 ms	6604 KB	Output is correct
38	Correct	4 ms	6604 KB	Output is correct
39	Correct	4 ms	6520 KB	Output is correct
40	Correct	306 ms	20224 KB	Output is correct
41	Correct	290 ms	18908 KB	Output is correct
42	Correct	289 ms	18964 KB	Output is correct
43	Correct	93 ms	11700 KB	Output is correct
44	Correct	114 ms	11896 KB	Output is correct
45	Correct	240 ms	17680 KB	Output is correct
46	Correct	259 ms	17528 KB	Output is correct
47	Correct	325 ms	19700 KB	Output is correct
48	Correct	120 ms	11120 KB	Output is correct
49	Correct	256 ms	19832 KB	Output is correct
50	Correct	262 ms	17828 KB	Output is correct
51	Correct	228 ms	17680 KB	Output is correct