Submission #1287847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287847		tminh	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	260 ms	26648 KiB

ho_t4

#include "bits/stdc++.h"
using namespace std;

#define task ""
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define vall(a) (a).begin(), (a).end()
#define sze(a) (int)a.size()
#define pii pair<ll, int>
#define pll pair<ll, ll>


#define ep emplace_back
#define pb push_back
#define pf push_front


const ll mod = 1e9 + 7;
const int N = 1e6 + 5;
const ll oo = 1e18;

bool START;

int n, m;

ll d[205][4];

vector<pair<int, ll>> adj[205], radj[205];
priority_queue<pii, vector<pii>, greater<pii>> q;
void dijkstra(int s, int idx) {
	while(!q.empty()) q.pop();
	for (int i = 1; i <= n; ++i) d[i][idx] = oo;
	d[s][idx] = 0;
	q.push(make_pair(d[s][idx], s));
	while(!q.empty()) {
		auto[c, u] = q.top();
		q.pop();
		
		if (c != d[u][idx]) continue;
		
		
		if (!(idx & 1)) {
			for (auto[v, w] : adj[u]) {
				if (d[v][idx] > d[u][idx] + w) {
					d[v][idx] = d[u][idx] + w;
					q.push(make_pair(d[v][idx], v));
				}
			}
		} else {
			for (auto[v, w] : radj[u]) {
				if (d[v][idx] > d[u][idx] + w) {
					d[v][idx] = d[u][idx] + w;
					q.push(make_pair(d[v][idx], v));
				}
			}
		}
		
	}
}


ll D[205];
ll calcdist(int s, int t) {
	for (int i = 1; i <= n; ++i) D[i] = oo;
	D[s] = 0;
	q.push(make_pair(D[s], s));
	while(!q.empty()) {
		auto[c, u] = q.top();
		q.pop();
		if (c != D[u]) continue;
		for (auto[v, w] : adj[u]) {
			if (D[v] > D[u] + w) {
				D[v] = D[u] + w;
				q.push(make_pair(D[v], v));
			}
		}
	}
	return D[t];
}

struct edge {
	int u, v;
	ll c, d;
	edge(int u_ = 0, int v_ = 0, ll c_ = 0, ll d_ = 0) : u(u_), v(v_), c(c_), d(d_) {}
} E[N];

inline void solve() {
	dijkstra(1, 0);
	dijkstra(1, 1);
	
	dijkstra(n, 2);
	dijkstra(n, 3);
	
	
	ll ans = d[n][0] + d[1][2];
	
	for (int i = 1; i <= m; ++i) {
		auto[u, v, c, w] = E[i];
		ll st = min(d[n][0], d[v][0] + c + d[u][3]);
		ll ts = min(d[1][2], d[v][2] + c + d[u][1]);
		
		if (ts + st + w < ans) {
			adj[u].erase(find(vall(adj[u]), make_pair(v, c)));
			adj[v].pb(make_pair(u, c));
			
			ans = min(ans, calcdist(1, n) + calcdist(n, 1) + w);
			
			adj[v].erase(find(vall(adj[v]), make_pair(u, c)));
			adj[u].pb(make_pair(v, c));
			
		}
	}
	cout << (ans > (oo / 2) ? -1 : ans);
}


inline void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
    	int u, v;
    	ll c, d;
    	cin >> u >> v >> c >> d;
    	adj[u].pb(make_pair(v, c));
    	radj[v].pb(make_pair(u, c));
    	
    	E[i] = edge(u, v, c, d);
    }
    return solve();
}
bool END;

int main() {
    if(fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    input();
    
    
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
    cerr << "Memory: " << fabs ((&END - &START)) / 1048576.0 << "MB\n";
    return 0;
}
//2911

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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