Submission #1286604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286604		third	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	564 ms	8284 KiB

ho_t4

#include<bits/stdc++.h>
typedef long long ll;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 200005
#define LOG 17
using namespace std;

// da doc sol

// y tuong ban dau: thu dao chieu cac canh, xong dung d 1 -> v + d u -> n

// trien khai: nhung canh nam tren duong di ngan nhat (duy nhat) se bi anh huong => ta lam thanh 1 cay
// dijsktra lai voi n - 1 canh nay, thu bo canh day di

// fix TLE: thay vi dijstktra lai tat cac cac dinh trace, ta dijstra tren duong di ngan nhat thoi
// nhung vi sao

// giai dap: neu u-v thuoc ddnn, => cost moi se tang, nen neu no ko thuoc, don gian truong hop do no se lay duong di ngan nhat ban dau

bool ghuy4g;

const ll inf = 1e16;

struct Canh {
	ll u, v, c, w;
} canh[50004];

ll n, m;
vector<pii> adj[2][N];

int d[2][2][205][205];

ll trace[2][2][205][205], ans = inf;

vector<ll> vt[2][2];

ll is[50004][2][2]; // canh do, voi t0, t1 co bi nam tren duong di hay khong

void dij(ll t0, ll t1, ll t2, ll st) {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 1; i <= n; i ++) {
		d[t0][t1][t2][i] = inf;
	}
	d[t0][t1][t2][st] = 0;
	pq.push({d[t0][t1][t2][st], st});
	while (pq.size()) {
		auto u = pq.top().se;
		auto c = pq.top().fi;
		pq.pop();
		if (c > d[t0][t1][t2][u]) continue;
		for (auto v : adj[t1][u]) {
			if (t2 > 0 && v.se == vt[t0][t1][t2 - 1]) continue;
			if (d[t0][t1][t2][v.fi] > c + canh[v.se].c) {
				d[t0][t1][t2][v.fi] = c + canh[v.se].c;
				trace[t0][t1][t2][v.fi] = v.se;
				pq.push({d[t0][t1][t2][v.fi], v.fi});
			}
		}
	}
}

void tv(ll t0, ll t1, ll st) {
	/*for (int i = 1; i <= n; i ++) {
		if (i == st) continue;
		ll id = trace[t0][t1][0][i];
		vt[t0][t1].push_back(id);
		is[id][t0][t1] = vt[t0][t1].size();
		dij(t0, t1, vt[t0][t1].size(), st);
	}*/
	for (int i = 1; i <= n; i ++) {
		if (i == st) continue;
		ll id = trace[t0][t1][0][i];
		ll u = canh[id].u, v = canh[id].v, c = canh[id].c;
		if (t1 == 0) {
			if (t0 == 0) {
				if (d[0][0][0][u] + c + d[1][1][0][v] != d[0][0][0][n]) {
					continue;
				}
			}
			else {
				if (d[1][0][0][u] + c + d[0][1][0][v] != d[1][0][0][1]) {
					continue;
				}
			}
		}
		else if (t1 == 1) {
			if (t0 == 0) {
				if (d[0][0][0][v] + c + d[1][1][0][u] != d[0][0][0][n]) {
					continue;
				}
			}
			else {
				if (d[1][0][0][v] + c + d[0][1][0][u] != d[1][0][0][1]) {
					continue;
				}
			}
		}
		vt[t0][t1].push_back(id);
		is[id][t0][t1] = vt[t0][t1].size();
		dij(t0, t1, vt[t0][t1].size(), st);
	}
}

void pre() {
	dij(0, 0, 0, 1); // tu 1
	dij(1, 0, 0, n); // tu n
	
	dij(0, 1, 0, 1); // den 1
	dij(1, 1, 0, n); // den n
	
	tv(0, 0, 1);
	tv(1, 0, n);
	
	tv(0, 1, 1);
	tv(1, 1, n);
}

void solve() {
	ans = min(ans, d[0][0][0][n] + d[1][0][0][1]);
	//cout << ans << endl;
	for (int i = 1; i <= m; i ++) {
		ll u = canh[i].u, v = canh[i].v, e = canh[i].w + canh[i].c;
		// chieu di dis1 = d1 + e + d2;
		ll d1 = d[0][0][is[i][0][0]][v];
		ll d2 = d[1][1][is[i][1][1]][u];
		ll dis1 = min(d[0][0][is[i][0][0]][n], d1 + e + d2);
		
		ll go_not = d[0][0][is[i][0][0]][n];
		ll go_use = d1 + d2 + canh[i].c;
		
		// chieu ve dis2 = d1 + e + d2;
		d1 = d[1][0][is[i][1][0]][v];
		d2 = d[0][1][is[i][0][1]][u];
		ll dis2 = min(d[1][0][is[i][1][0]][1], d1 + d2 + e);
		
		ll back_not = d[1][0][is[i][1][0]][1];
		ll back_use = d1 + d2 + canh[i].c;
		
		ans = min(ans, canh[i].w + min(go_not, go_use) + min(back_not, back_use));
		
	}
	if (ans >= inf) ans = -1;
	cout << ans;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
    	ll u, v, c, w;
    	cin >> u >> v >> c >> w;
    	adj[0][u].push_back({v, i});
    	adj[1][v].push_back({u, i});
    	canh[i] = {u, v, c, w};
    }
    pre();
    
    solve();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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