Submission #497132

#	Time	Username	Problem	Language	Result	Execution time	Memory
497132		saarang123	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	204 ms	2884 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxn = 203;
const ll inf = 1e12;
vector<vector<ll>> adj, rev;
vector<vector<bool>> inpath;
vector<array<int, 2>> edges[mxn][mxn];
int n, m;

vector<int> dijkstra(int src, vector<ll> &dist, vector<vector<ll>> &g) {
	dist = vector<ll>(n, inf);
	dist[src] = 0;
	vector<int> p(n, -1);
	vector<bool> vis(n, false);
	while(true) {
		pair<ll, int> mn = {inf, -1};
		for(int i = 0; i < n; i++) if(!vis[i])
			mn = min(mn, {dist[i], i});

		if(mn.first >= inf)
			break;
		vis[mn.second] = true;
		for(int u = 0; u < n; u++) {
			if(g[mn.second][u] >= inf) continue;
			ll ndist = mn.first + g[mn.second][u];
			if(ndist < dist[u]) {
				dist[u] = ndist;
				p[u] = mn.second;
			}
		}
	}
	return p;
}

void extract(int end, vector<int> p) {
	vector<int> path;
	path.push_back(end);
	while(p[path.back()] > -1) 
		path.push_back(p[path.back()]);
	reverse(path.begin(), path.end());

	for(int i = 1; i < (int) path.size(); i++)
		inpath[path[i - 1]][path[i]] = true;
}

template<typename T>
void out(vector<T> a) {
	for(T x : a)
		cout << x << ' ';
	cout << endl;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    cin >> n >> m;
    adj = rev = vector<vector<ll>>(n, vector<ll>(n, inf));
    inpath = vector<vector<bool>>(n, vector<bool>(n, false));

    for(int u, v, c, d, i = 0; i < m; i++) {
    	cin >> u >> v >> c >> d;
    	u--, v--;
    	adj[u][v] = min(adj[u][v], (ll) c);
    	rev[v][u] = min(rev[v][u], (ll) c);
    	edges[u][v].push_back({c, d});
    }

    for(int i = 0; i < n; i++)
    	for(int j = 0; j < n; j++)
    		sort(edges[i][j].begin(), edges[i][j].end());

    vector<ll> d1, dn, r1, rn;
    extract(n - 1, dijkstra(0, d1, adj));
    extract(0, dijkstra(n - 1, dn, adj));
    dijkstra(0, r1, rev);
    dijkstra(n - 1, rn, rev);

    //out(d1); out(dn); out(r1); out(rn);

    ll ans = d1[n - 1] + dn[0];
    for(int u = 0; u < n; u++) {
    	for(int v = 0; v < n; v++) if(!edges[u][v].empty()) {
    		if(inpath[u][v]) {
    			ll uv = adj[u][v], vu = adj[v][u];
    			adj[u][v] = (edges[u][v].size() > 1 ? edges[u][v][1][0] : inf);
    			adj[v][u] = edges[u][v][0][0];

    			vector<ll> nd1, ndn;
    			dijkstra(0, nd1, adj);
    			dijkstra(n - 1, ndn, adj);
    			ll cost = nd1[n - 1] + ndn[0] + edges[u][v][0][1];
    			ans = min(ans, cost);

    			adj[u][v] = uv;
    			adj[v][u] = vu;
    		} 

    		for(int i = 0 + inpath[u][v]; i < (int) edges[u][v].size(); i++) {
    			auto [c, d] = edges[u][v][i];
    			ll c1 = d1[v] + rn[u] + c + d; //1 -> v -> u -> n
    			ll c2 = dn[v] + r1[u] + c + d; //n -> v -> u -> 1
    			ans = min({ans, c1 + dn[0], c2 + d1[n - 1], c1 + c2 - d});
    		}
    	}
    }

    cout << (ans >= inf ? -1 : ans) << '\n';
    return 0;
}

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