Submission #1194476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194476		baodat	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	58 ms	3492 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define eb emplace_back
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FORD(i, l, r) for (int i = (l); i >= (r); i--)
const int oo = 1e18;
typedef pair<int,int> pii;
void readFile() {
#define NAME "train"
	freopen(NAME ".INP", "r", stdin);
	freopen(NAME ".OUT", "w", stdout);
}
const int N = 5e4 + 5;
int dp[505][505], ds[505], a[N], b[N], w[N], c[N];
vector<int> adj[505];
bool visited[505];
int n, m;
template<typename T> void minimize(T& a, T b) {
	a = min(a, b);
}
template<typename T> void maximize(T& a, T b) {
	b = max(a, b);
}
int dijkstra(int s, int t) {
	fill(ds, ds + n + 1, oo);
	fill(visited, visited + n, false);
	ds[s] = 0;
	FOR(i, 0, n - 1) {
		int u = n;
		FOR(v, 0, n - 1) if(!visited[v] && ds[v] < ds[u]) u = v;
		visited[u] = 1;
		if(ds[u] == oo) break;
		for(int e : adj[u]) minimize(ds[b[e]], ds[u] + w[e]);
	}
	return ds[t];
}
void solve() {
	cin >> n >> m;
	FOR(i, 0, n - 1)FOR(j, 0, n - 1) dp[i][j] = (i == j ? 0 : oo);
	FOR(i, 0, m - 1) {
		cin >> a[i] >> b[i] >> w[i] >> c[i];
		--a[i];
		--b[i];
		minimize(dp[a[i]][b[i]], w[i]);
		adj[a[i]].pb(i);
	}
	FOR(i, 0, n - 1)FOR(u, 0, n - 1)FOR(v, 0, n - 1) minimize(dp[u][v], dp[u][i] + dp[i][v]);
	int s = 0, t = n - 1, ans = dp[s][t] + dp[t][s];
	FOR(i, 0, m - 1) {
		int to = min(dp[s][t], dp[s][b[i]] + w[i] + dp[a[i]][t]);
		int from = min(dp[t][s], dp[t][b[i]] + w[i] + dp[a[i]][s]);
		if(c[i] + to + from < ans) {
			adj[a[i]].erase(find(all(adj[a[i]]), i));
			swap(a[i], b[i]);
			adj[a[i]].pb(i);
			minimize(ans, c[i] + dijkstra(s, t) + dijkstra(t, s));
			adj[a[i]].pop_back();
			swap(a[i], b[i]);
			adj[a[i]].pb(i);
		}
	}
	cout << (ans < oo ? ans : -1);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//readFile();
	int t = 1;
	while(t--) solve();
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'void readFile()':
ho_t4.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen(NAME ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen(NAME ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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