Submission #1176488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176488		Tsagana	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	58 ms	3504 KiB

ho_t4

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

const int inf = 1e18;

int n;
int dp[510][510], ds[510];
int a[50010], b[50010], w[50010], c[50010];
vector<int> adj[510];
bool vis[510];

void fmn(int &a, int b) {a = min(a, b);}
void fmx(int &a, int b) {b = max(a, b);}

int dij(int s, int t) {
	fill(ds, ds + n + 1, inf);
	fill(vis, vis + n, false);
	ds[s] = 0;
	for (int i = 0; i < n; i++) {
		int u = n;
		for (int v = 0; v < n; v++) if (!vis[v] && ds[v] < ds[u]) u = v;
		vis[u] = 1;
		if (ds[u] == inf) break ;
		for (int e: adj[u]) fmn(ds[b[e]], ds[u] + w[e]);
	}
	return ds[t];
}

void solve () {
	int m; cin >> n >> m;
	
	for (int u = 0; u < n; u++)
	for (int v = 0; v < n; v++)
		dp[u][v] = (u == v ? 0 : inf);
	
	for (int e = 0; e < m; e++) {
		cin >> a[e] >> b[e] >> w[e] >> c[e], --a[e], --b[e];
		fmn(dp[a[e]][b[e]], w[e]);
		adj[a[e]].pb(e);
	}

	for (int w = 0; w < n; w++)
	for (int u = 0; u < n; u++)
	for (int v = 0; v < n; v++)
		fmn(dp[u][v], dp[u][w] + dp[w][v]);

	int s = 0, t = n - 1,  ans = dp[s][t] + dp[t][s];
	for (int e = 0; e < m; e++) {
		int to = min(dp[s][t], dp[s][b[e]] + w[e] + dp[a[e]][t]);
		int fr = min(dp[t][s], dp[t][b[e]] + w[e] + dp[a[e]][s]);
		if (c[e] + to + fr < ans) {
			adj[a[e]].erase(find(all(adj[a[e]]), e));
			swap(a[e], b[e]);
			adj[a[e]].pb(e);
			fmn(ans, c[e] + dij(s, t) + dij(t, s));
			adj[a[e]].pp();
			swap(a[e], b[e]);
			adj[a[e]].pb(e);
		}
	}

	cout << (ans < inf ? ans : -1);
}
signed main() {IOS solve(); return 0;}

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