Submission #485500

#	Time	Username	Problem	Language	Result	Execution time	Memory
485500		socho	Robot (JOI21_ho_t4)	C++14	34 / 100	316 ms	64440 KiB

Main

/*
	Going for ST1
*/
#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;

int n, m;
const int MXN = 1005;
const int MXM = 2005;
int a[MXM], b[MXM], colour[MXM], price[MXM];
vector<pair<int, int>> adj[MXN];
int dist[MXN][MXM][2];
map<int, map<int, int>> adj_count;
map<int, map<int, int>> adj_sum;

signed main() {

	ran(); fast();

	for (int i=0; i<MXN; i++) for (int j=0; j<MXM; j++) dist[i][j][0] = dist[i][j][1] = LLONG_MAX / 4;

	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		cin >> a[i] >> b[i] >> colour[i] >> price[i];
		adj[a[i]].push_back({i, b[i]});
		adj[b[i]].push_back({i, a[i]});
		adj_count[a[i]][colour[i]]++;
		adj_count[b[i]][colour[i]]++;
		adj_sum[a[i]][colour[i]]+=price[i];
		adj_sum[b[i]][colour[i]]+=price[i];
	}
	
	// initially at node 1, previous road '0', was not changed, price is 0
	
	min_pq<pair<int, pair<pair<int, int>, int>>> process;
	process.push({0, {{1, 0}, 0}}); // node, prevroad, didwechange
	
	int ans = LLONG_MAX;
	
	while (!process.empty()) {
		
		auto x = process.top(); process.pop();
		int di = x.first;
		int node = x.second.first.first;
		int prevroad = x.second.first.second;
		int waschanged = x.second.second;
		
		if (node == n) {
			ans = min(ans, di);
		}
		
		// cout << node << ' ' << prevroad << " " << waschanged << ": " << di << endl;
		if (dist[node][prevroad][waschanged] < di) {
			continue;
		}
		
		dist[node][prevroad][waschanged] = di;
		
		for (auto x: adj[node]) {
			int road = x.first, other = x.second;
			// what is the cost of going there?
			if (road == prevroad) continue; // don't go back the previous road, why would you?
			if (adj_count[node][colour[road]] == 1) {
				// then it's free!
				if (di < dist[other][road][0]) {
					process.push({di, {{other, road}, 0}});
					dist[other][road][0] = di;
				}
			}
			else {
				// there's a lot of these roads with this colour, so we must change something
				int cost_change = price[road]; // what is the cost of changing this road, so we can use it?
				int cost_others = adj_sum[node][colour[road]] - cost_change; // what is the cost of changing all the other roads?
				if (colour[prevroad] == colour[road]) {
					// the old road is one of those other roads
					if (waschanged) {
						// old road colour already changed, don't change again!
						cost_others -= price[prevroad];
					}
				}
				
				assert(cost_change >= 0);
				assert(cost_others >= 0);
				
				// now we consider changing this road:
				
				if (di + cost_change < dist[other][road][1]) {
					process.push({di + cost_change, {{other, road}, 1}});
					dist[other][road][1] = di + cost_change;
				}
				// or changing all other roads:
				if (di + cost_others < dist[other][road][0]) {
					process.push({di + cost_others, {{other, road}, 0}});
					dist[other][road][0] = di + cost_others;
				}
			}
		}
		
	}
	
	if (ans == LLONG_MAX) cout << -1 << endl;
	else cout << ans << endl;

}

Compilation message (stderr)

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

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42