Submission #861076

#	Time	Username	Problem	Language	Result	Execution time	Memory
861076		phoenix0423	Olympic Bus (JOI20_ho_t4)	C++17	16 / 100	1087 ms	20692 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[50000 + 4];

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);
	dist[0] = 0, dist2[n - 1] = 0, rdist[n - 1] = 0, rdist2[0] = 0;
	auto dijkstra = [&](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 : adj[id]){
				if(invalid[x]) continue;
				auto [a, b, c, d] = e[x];
				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);
	dijkstra(dist2);
	rdijkstra(rdist);
	rdijkstra(rdist2);
	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((dist[a] < INF && rdist[b] < INF && dist[a] + rdist[b] + c == dist[n - 1] && dist[n - 1] < INF) || (dist2[a] < INF && rdist2[b] < INF && dist2[a] + rdist2[b] + c == dist2[0] && dist2[0] < INF)){
			cnt++;
			// 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), dijkstra(ndist2);
			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";
}

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