Submission #485062

#	Time	Username	Problem	Language	Result	Execution time	Memory
485062		socho	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	316 ms	4100 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define endl '\n'
// #define double long double
#define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;
// #define cerr if(0) cerr
#define debug(x) cerr << #x << ": " << x << endl;

#define int long long
int n, m;
const int MXN = 205, MXM = 50005;
 
int apsp[MXN][MXN];
int eds[MXM][4];
 
vector<int> adj[MXN];
int mxh = INT_MAX * 1000ll;
 
int dist(int src, int dest, int skip) {
	int dists[MXN];
	for (int i=0; i<MXN; i++) dists[i] = mxh;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> proc;
	proc.push({0, src});
	while (!proc.empty()) {
		auto x = proc.top(); proc.pop();
		int di = x.first, no = x.second;
		if (dists[no] < di) continue;
		dists[no] = di;
		for (auto ed: adj[no]) {
			if (ed != skip) {
				int ot = eds[ed][0] + eds[ed][1] - no;
				int we = eds[ed][2];
				if (dists[ot] > dists[no] + we) {
					dists[ot] = dists[no] + we;
					proc.push({dists[ot], ot});
				}
			}
		}
		if (no == eds[skip][1]) {
			int ot = eds[skip][0];
			int od = dists[no] + eds[skip][2];
			if (dists[ot] > od) {
				dists[ot] = od;
				proc.push({od, ot});
			}
		}
	}
	return dists[dest];
} 
 
signed main() {
	
	ran(); fast();
	
	for (int i=0; i<MXN; i++) {
		for (int j=0; j<MXN; j++) {
			apsp[i][j] = mxh;
		}
		apsp[i][i] = 0;
	}
	
	cin >> n >> m;
	for (int i=0; i<m; i++) {
		int a, b, w, c;
		cin >> a >> b >> w >> c;
		eds[i][0] = a;
		eds[i][1] = b;
		eds[i][2] = w;
		eds[i][3] = c;
		adj[a].push_back(i);
		apsp[a][b] = min(apsp[a][b], w);
	}
	
	for (int k=1; k<=n; k++) {
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				if (apsp[i][k] + apsp[k][j] < apsp[i][j]) {
					apsp[i][j] = apsp[i][k] + apsp[k][j];
				}
			}
		}
	}
	
	int res = apsp[1][n] + apsp[n][1];
	for (int i=0; i<m; i++) {
		int a = eds[i][0], b = eds[i][1];
		int w = eds[i][2], c = eds[i][3];
		int d1 = min(apsp[1][n], apsp[1][b] + w + apsp[a][n]);
		int d2 = min(apsp[n][1], apsp[n][b] + w + apsp[a][1]);
		if (d1 + c + d2 < res) {
			int actual = dist(1, n, i) + dist(n, 1, i) + c;
			res = min(res, actual);
		}
	}
	
	if (res >= mxh) cout << -1 << endl;
	else cout << res << endl;
	
}

Compilation message (stderr)

ho_t4.cpp: In function 'void usaco()':
ho_t4.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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