Submission #513634

#	Time	Username	Problem	Language	Result	Execution time	Memory
513634		CSQ31	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	377 ms	5832 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 5e4+5;
const ll INF = 1e18;
#define sz(a) (int)(a.size())
ll c[MAXN],d[MAXN];
int n,m;
array<int,2>spar[201],tpar[201],par[201];
vector<array<int,2>>g[201],gr[201];
bool block[MAXN],vis[201];
 
//distances 
ll dist[201];
ll from_s[201],from_t[200];
ll to_s[201],to_t[200];
void djikstra(int v,vector<array<int,2>>*g,ll *dist,array<int,2>*par){
	dist[0] = INF;
	for(int i=1;i<=n;i++)dist[i] = INF,vis[i] = 0;
	dist[v] = 0;
	while(true){
		int u = 0;
		for(int i=1;i<=n;i++)if(dist[i] < dist[u] && !vis[i])u = i;
		if(!u)break;
		vis[u] = 1;
		for(auto x:g[u]){
			if(block[x[1]])continue;
			if(dist[u] + c[x[1]] < dist[x[0]]){
				dist[x[0]] = dist[u] + c[x[1]];
				par[x[0]] = {u,x[1]};
			}
		}
	}
}
ll s_to_t[2][MAXN],t_to_s[2][MAXN];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	vector<array<int,2>>edge;
	for(int i=0;i<m;i++){
		int v,u;
		cin>>v>>u>>c[i]>>d[i];
		g[v].push_back({u,i});
		gr[u].push_back({v,i});
		edge.push_back({v,u});
	}
	djikstra(1,g,from_s,spar);
	ll none = from_s[n];
	for(int i=0;i<m;i++)s_to_t[0][i] = from_s[n];
	//first case not use inverted path at all
	//some might intersect so bad
	if(from_s[n] != INF){
		int cur = n;
		while(cur != 1){
			int p = spar[cur][1];
			block[p] = 1;
			djikstra(1,g,dist,par);
			s_to_t[0][p] = dist[n];
			block[p] = 0;
			cur = spar[cur][0];
		}
	}
	//second case invert v->u
	//use 1->u->v then v->n
	//1->u can't use 1->v->u since v->u can only be the last edge only need to consider another last edge if v->u just happens to be used in best path
	//v->n cant use v->u->n can be treated similarly as 1->u
	djikstra(n,gr,to_t,tpar);
	for(int i=0;i<m;i++){
		int v = edge[i][0],u = edge[i][1];
		ll cost = from_s[u] + to_t[v] + c[i];
		if(spar[u][1] == i){
			cost-=from_s[u];
			block[spar[u][1]] = 1;
			djikstra(1,g,dist,par);
			cost+=dist[u];
			block[spar[u][1]] = 0;
		}
		if(tpar[v][1] == i){
			cost-=to_t[v];
			block[tpar[v][1]] = 1;
			djikstra(n,gr,dist,par);
			cost+=dist[v];
			block[tpar[v][1]] = 0;
		}
		s_to_t[1][i] = cost;
	}
	///////////// n->t;
	djikstra(n,g,from_t,tpar);
	none+=from_t[1];
	for(int i=0;i<m;i++)t_to_s[0][i] = from_t[1];
	if(from_t[1] != INF){
		int cur = 1;
		while(cur != n){
			int p = tpar[cur][1];
			block[p] = 1;
			djikstra(n,g,dist,par);
			t_to_s[0][p] = dist[1];
			block[p] = 0;
			cur = tpar[cur][0];
		}
	}
 
	djikstra(1,gr,to_s,spar);
	for(int i=0;i<m;i++){
		int v = edge[i][0],u = edge[i][1];
		ll cost = from_t[u] + to_s[v] + c[i];
		if(tpar[u][1] == i){
			cost-=from_t[u];
			block[tpar[u][1]] = 1;
			djikstra(n,g,dist,par);
			cost+=dist[u];
			block[tpar[u][1]] = 0;
		}
		if(spar[v][1] == i){
			cost-=to_s[v];
			block[spar[v][1]] = 1;
			djikstra(1,gr,dist,par);
			cost+=dist[v];
			block[spar[v][1]] = 0;
		}
		t_to_s[1][i] = cost;
	}
	
	ll ans = min(INF,none);
	for(int i=0;i<m;i++){
		ans = min(ans,s_to_t[0][i] + t_to_s[0][i]);
		ans = min(ans,min(s_to_t[1][i],s_to_t[0][i]) + min(t_to_s[1][i],t_to_s[0][i]) + d[i]); 
	}
	if(ans == INF)ans=-1;
	cout<<ans<<'\n';
	
	
}

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