Submission #861087

#	Time	Username	Problem	Language	Result	Execution time	Memory
861087		phoenix0423	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	237 ms	22092 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 4e5 + 5;
const ll INF = 2e9 + 7;
struct edge{
	int a, b, c, d;
	edge(){}
	edge(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d){}
};
int n, m;
vector<int> adj[maxn], radj[maxn];
vector<edge> e;
int invalid[50004], crit[50004];

int main(void){
	fastio;
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int a, b, c, d;
		cin>>a>>b>>c>>d;
		a--, b--;
		adj[a].pb(i);
		radj[b].pb(i);
		e.pb(edge(a, b, c, d));
	}
	vector<ll> dist(n, INF), dist2(n, INF), rdist(n, INF), rdist2(n, INF);
	vector<int> from(n), from2(n);
	dist[0] = 0, dist2[n - 1] = 0, rdist[n - 1] = 0, rdist2[0] = 0;
	auto dijkstra = [&](vector<ll>& dist, vector<int>& from) -> void{
		vector<int> vis(n);
		for(int i = 0; i < n; i++){
			ll mn = INF, id = 0;
			for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
			vis[id] = 1;
			for(auto x : adj[id]){
				if(invalid[x]) continue;
				auto [a, b, c, d] = e[x];
				if(dist[b] > dist[a] + c) from[b] = a;
				dist[b] = min(dist[b], dist[a] + c);
			}
		}
	};
	auto rdijkstra = [&](vector<ll>& dist) -> void{
		vector<int> vis(n);
		for(int i = 0; i < n; i++){
			ll mn = INF, id = 0;
			for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
			vis[id] = 1;
			for(auto x : radj[id]){
				auto [a, b, c, d] = e[x];
				dist[a] = min(dist[a], dist[b] + c);
			}
		}
	};
	dijkstra(dist, from);
	dijkstra(dist2, from2);
	rdijkstra(rdist);
	rdijkstra(rdist2);
	auto find_crit = [&](int st, int ed, vector<ll> &dist, vector<int> &from){
		if(dist[ed] >= INF) return;
		int pos = ed;
		while(pos != st){
			int org = pos;
			for(auto x : radj[pos]){
				auto [a, b, c, d] = e[x];
				if(dist[pos] == dist[a] + c && from[pos] == a){
					crit[x] = 1;
					pos = a;
					break;
				}
			}
		}
	};
	find_crit(0, n - 1, dist, from);
	find_crit(n - 1, 0, dist2, from2);
	ll ans = dist[n - 1] + dist2[0];
	int cnt = 0;
	for(int i = 0; i < m; i++){
		auto [a, b, c, d] = e[i];
		if(crit[i]){
			cnt++;
			if(cnt > n * 2) break;
			// if(cnt > n * 10) break;
			invalid[i] = 1;
			e.pb(edge(b, a, c, d));
			adj[b].pb(m);
			vector<ll> ndist(n, INF), ndist2(n, INF);
			ndist[0] = 0, ndist2[n - 1] = 0;
			dijkstra(ndist, from), dijkstra(ndist2, from);
			ans = min(ans, ndist[n - 1] + ndist2[0] + d);
			e.pop_back();
			adj[b].pop_back();
			invalid[i] = 0;
			continue;
		}
		//invert : becomes b->a
		ll d1 = min(dist[n - 1], dist[b] + rdist[a] + c);
		ll d2 = min(dist2[0], dist2[b] + rdist2[a] + c);
		ans = min(ans, d1 + d2 + d);
	}
	cout<<(ans < INF ? ans : -1)<<"\n";
}

Compilation message (stderr)

ho_t4.cpp: In lambda function:
ho_t4.cpp:74:8: warning: unused variable 'org' [-Wunused-variable]
   74 |    int org = pos;
      |        ^~~

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