Submission #442778

#	Time	Username	Problem	Language	Result	Execution time	Memory
442778		aryan12	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1088 ms	4692 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct edge {
	int v, u, cost, rev_cost, idx;
};

const int N = 205, INF = 1e15;
int n, m;
int dist[N][N];
bool used[3][N];
vector<edge> edges;

int dijkstra(int src, int dest, int d) {
	int prev[N], cur_dist[N];
	vector<array<int, 3> > g[N];
	for(int i = 0; i < edges.size(); i++) {
		g[edges[i].v].push_back({edges[i].u, edges[i].cost, i});
		//cout << "tuple = (" << edges[i].v << ", " << edges[i].u << ", " << edges[i].cost << ", " << i << ")\n";
	}
	for(int i = 0; i < N; i++) {
		prev[i] = -1;
		cur_dist[i] = INF;
	}
	cur_dist[src] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.push(make_pair(0, src));
	while(!pq.empty()) {
		int dis = pq.top().first, node = pq.top().second;
		pq.pop();
		if(dis > cur_dist[node]) {
			continue;
		}
		for(int i = 0; i < g[node].size(); i++) {
			if(cur_dist[g[node][i][0]] > cur_dist[node] + g[node][i][1]) {
				cur_dist[g[node][i][0]] = cur_dist[node] + g[node][i][1];
				prev[g[node][i][0]] = g[node][i][2];
				pq.push(make_pair(cur_dist[g[node][i][0]], g[node][i][0]));
			}
		}
	}
	/*cout << "cur_dist array\n";
	for(int i = 1; i <= n; i++) {
		cout << cur_dist[i] << " ";
	}
	cout << "\n";
	cout << "prev array\n";
	for(int i = 1; i <= n; i++) {
		cout << prev[i] << " ";
	}
	cout << "\n";*/
	if(cur_dist[dest] < INF) {
		int cur = dest;
		while(cur != src) {
			used[d][prev[cur]] = true;
			cur = edges[prev[cur]].v;
		}
	}
	return cur_dist[dest];
}

int canChange(int src, int dest, int idx) {
	//cout << "src = " << src << ", edges[idx].u = " << edges[idx].u << ", edges[idx].v = " << edges[idx].v << ", dest = " << dest << "\n";
	if(dist[src][edges[idx].v] != INF && dist[edges[idx].u][dest] != INF) {
		return min(dist[src][edges[idx].v] + dist[edges[idx].u][dest] + edges[idx].cost, dist[src][dest]);
	}
	return dist[src][dest];
}

void Solve() {
	cin >> n >> m;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			dist[i][j] = INF;
		}
		dist[i][i] = 0;
		used[0][i] = false;
		used[1][i] = false;
	}
	edge e;
	for(int i = 0; i < m; i++) {
		cin >> e.v >> e.u >> e.cost >> e.rev_cost;
		e.idx = i;
		dist[e.v][e.u] = min(dist[e.v][e.u], e.cost);
		edges.push_back(e);
	}
	for(int k = 1; k <= n; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}
	/*cout << "Outputting distances\n";
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cout << dist[i][j] << " ";
		}
		cout << "\n";
	}*/
	int ans = min(INF, dist[1][n] + dist[n][1]);
	dijkstra(1, n, 0);
	dijkstra(n, 1, 1);
	/*cout << "Edges in path 1 to n\n";
	for(int i = 0; i < m; i++) {
		cout << used[0][i] << " ";
	}
	cout << "\n";
	cout << "Edges in path n to 1\n";
	for(int i = 0; i < m; i++) {
		cout << used[1][i] << " ";
	}
	cout << "\n";
	cout << "ans = " << ans << "\n";*/
	for(int i = 0; i < m; i++) {
		swap(edges[i].v, edges[i].u);
		int cur_ans = (used[0][i]) ? dijkstra(1, n, 2) : canChange(1, n, i);
		int x = (used[1][i]) ? dijkstra(n, 1, 2) : canChange(n, 1, i);
		//cout << "Current index = " << i << "\n";
		//cout << "cur_ans = " << cur_ans << ", x = " << x << ", isUsed 1 to n? " << used[0][i] << ", isUsed n to 1? " << used[1][n] << "\n";
		cur_ans += x;
		if(cur_ans < INF) {
			ans = min(ans, cur_ans + edges[i].rev_cost);
		}
		swap(edges[i].v, edges[i].u);
	}
	if(ans >= INF) {
		cout << "-1\n";
	}
	else {
		cout << ans << "\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'long long int dijkstra(long long int, long long int, long long int)':
ho_t4.cpp:20:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
ho_t4.cpp:37:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int i = 0; i < g[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

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