Submission #529398

#	Time	Username	Problem	Language	Result	Execution time	Memory
529398		rk42745417	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1055 ms	4552 KiB

ho_t4

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

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(4e18) + ll(2e15);
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int N = 207, M = 5e4 + 25;
struct dat {
	int v, c, i;
};
vector<dat> edge[N], redge[N];
int n;
ll cost[M], len[M], dis1[N], disn[N];
pair<int, int> edges[M];

ll dijk(int s, int t, int id) {
	vector<ll> dis(n + 1, LINF);
	vector<bool> vis(n + 1);
	dis[s] = 0;
	while(true) {
		int u = -1;
		for(int i = 1; i <= n; i++)
			if(!vis[i] && (u == -1 || dis[u] > dis[i]))
				u = i;
		if(u == -1)
			break;
		vis[u] = true;
		for(const auto &[v, c, i] : edge[u])
			if(i != id && dis[v] > dis[u] + c)
				dis[v] = dis[u] + c;
	}
	return dis[t];
}
ll brute(int id) {
	if(~id)
		edge[edges[id].second].push_back({edges[id].first, len[id], -1});
	ll ret = dijk(1, n, id) + dijk(n, 1, id);
	if(~id)
		edge[edges[id].second].pop_back();
	return ret;
}
signed main() {
	int m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, c, d;
		cin >> u >> v >> c >> d;
		edge[u].push_back({v, c, i});
		redge[v].push_back({u, c, i});
		cost[i] = d;
		len[i] = c;
		edges[i] = {u, v};
	}

	ll ans = brute(-1);
	for(int i = 0; i < m; i++) {
		ans = min(ans, brute(i) + cost[i]);
	}
	if(ans > 2e9)
		cout << "-1\n";
	else
		cout << ans << '\n';
}

Compilation message (stderr)

ho_t4.cpp: In function 'll brute(int)':
ho_t4.cpp:47:60: warning: narrowing conversion of 'len[id]' from 'll' {aka 'long int'} to 'int' [-Wnarrowing]
   47 |   edge[edges[id].second].push_back({edges[id].first, len[id], -1});
      |                                                      ~~~~~~^

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