Submission #1055257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055257		Alihan_8	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	205 ms	3528 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//~ #define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e12;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	
	int n, m; cin >> n >> m;
	
	// subtask #2
	
	vector <int> U(m), V(m), C(m), D(m);
	
	for ( int i = 0; i < m; i++ ){
		cin >> U[i] >> V[i] >> C[i] >> D[i];
		
		--U[i], --V[i];
	}
	
	vector <int> is(m);
	
	auto get = [&](auto U, auto V, auto C, int sx){
		vector <vector<ar<int,3>>> adj(n);
		
		for ( int i = 0; i < (int)U.size(); i++ ){
			int u = U[i], v = V[i];
			
			adj[u].pb({v, C[i], i});
		}
		
		vector <i64> dp(n, inf);
		vector <int> fa(n, -1);
		
		priority_queue <pair<i64,int>> q;
		
		q.push({0, sx}); dp[sx] = 0;
		
		while ( !q.empty() ){
			auto [val, u] = q.top();
			q.pop();
			
			if ( -val != dp[u] ) continue;
			
			for ( auto &[v, w, j]: adj[u] ){
				if ( chmin(dp[v], dp[u] + w) ){
					q.push({-dp[v], v});
					fa[v] = j;
				}
			}
		}
		
		for ( auto &x: fa ){
			if ( x != -1 ) is[x] = 1;
		}
		
		return dp;
	};
	
	auto f = [&](int j){
		auto calc = [&](int sx, int se){
			vector <vector<i64>> adj(n, vector <i64> (n, inf));
			
			for ( int i = 0; i < m; i++ ){
				int u = U[i], v = V[i];
				
				if ( i == j ) swap(u, v);
				
				chmin(adj[u][v], C[i]);
			}
			
			vector <i64> d(n, inf), us(n);
			
			d[sx] = 0;
			
			for ( int iter = 0; iter < n; iter++ ){
				int u = -1;
				
				for ( int v = 0; v < n; v++ ){
					if ( !us[v] && (u == -1 || d[u] > d[v]) ) u = v;
				}
				
				if ( u == se ) return d[u];
				
				us[u] = 1;
				
				for ( int v = 0; v < n; v++ ){
					chmin(d[v], d[u] + adj[u][v]);
				}
			}
			
			return inf;
		};
		
		return calc(0, n - 1) + calc(n - 1, 0) + D[j];
	};
	
	int s = 0, e = n - 1;
	
	auto fs = get(U, V, C, s), fe = get(U, V, C, e);
	auto IS = is;
	auto ts = get(V, U, C, s), te = get(V, U, C, e);
	
	i64 opt = fs[e] + fe[s];
	
	for ( int i = 0; i < m; i++ ){
		i64 x = min(fs[e], fs[V[i]] + C[i] + te[U[i]]);
		i64 y = min(fe[s], fe[V[i]] + C[i] + ts[U[i]]);
		
		if ( IS[i] ) chmin(opt, f(i));
		else chmin(opt, x + y + D[i]);
	}
	
	if ( opt >= inf ){
		opt = -1;
	}
	
	cout << opt;
	
    cout << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63