Submission #510205

#	Time	Username	Problem	Language	Result	Execution time	Memory
510205		CSQ31	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	316 ms	262148 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],dist[MAXN];
int n,m;
array<int,2>par[201];
vector<array<int,2>>g[201],gr[201];
bool block[MAXN],vis[201];
void djikstra(int v,vector<array<int,2>>*g){
	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 force[2][201],notused[2][201];
ll secbest[201];

vector<int>path;
vector<ll>cut;

int main()
{
	cin>>n>>m;
	ll thonk = 0;
	dist[0] = INF;
	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});
	}
	//second best paths for 1->v
	secbest[1] = INF;
	for(int i=2;i<=n;i++){
		block[par[i][1]] = 1;
		djikstra(1,g);
		secbest[i] = dist[i];
		block[par[i][1]] = 0;
	}
	//whats contribution if inverted ith edge is forced/forbidden on 1->n?
	djikstra(1,g);
	thonk+=dist[n];
	//v->u to u->v go to u first
	for(int i=0;i<m;i++){
		force[0][i] = dist[edge[i][1]];
		notused[0][i] = dist[n];
	}
	if(dist[n] != INF){
		int cur = n;
		while(cur!=1){
			path.push_back(par[cur][1]);
			cur = par[cur][0];
		}
		reverse(path.begin(),path.end());
		cut.resize(sz(path));
		for(int i=0;i<sz(path);i++){
			int x = path[i];
			block[x] = 1;
			djikstra(1,g);
			cut[i] = dist[n];	
			block[x] = 0;
		}
	}
	for(int i=0;i<sz(path);i++)notused[0][path[i]] = cut[i]; //take from cut if intersect
	for(int i=0;i<m;i++){
		int v = edge[i][1];
		if(i == par[v][1])force[0][i] = secbest[v]; //if intersect take second best edge instead
	}
	djikstra(n,gr);
	for(int i=0;i<m;i++)force[0][i]+=dist[edge[i][0]] + c[i];
	/*
	for(int i=0;i<m;i++)cout<<notused[0][i]<<" "; 
	cout<<'\n';
	for(int i=0;i<m;i++)cout<<force[0][i]<<" "; 
	cout<<'\n';
	* */
	//////
	secbest[1] = INF;
	for(int i=2;i<=n;i++){
		block[par[i][1]] = 1;
		djikstra(n,g);
		secbest[i] = dist[i];
		block[par[i][1]] = 0;
	}
	//whats contribution if inverted ith edge is forced/forbidden on 1->n?
	djikstra(n,g);
	thonk+=dist[1];
	//v->u to u->v go to u first
	for(int i=0;i<m;i++){
		force[1][i] = dist[edge[i][1]];
		notused[1][i] = dist[1];
	}
	if(dist[1] != INF){
		int cur = 1;
		while(cur!=n){
			path.push_back(par[cur][1]);
			cur = par[cur][0];
		}
		reverse(path.begin(),path.end());
		cut.resize(sz(path));
		for(int i=0;i<sz(path);i++){
			int x = path[i];
			block[x] = 1;
			djikstra(n,g);
			cut[i] = dist[1];	
			block[x] = 0;
		}
	}
	for(int i=0;i<sz(path);i++)notused[1][path[i]] = cut[i]; //take from cut if intersect
	for(int i=0;i<m;i++){
		int v = edge[i][1];
		if(i == par[v][1])force[1][i] = secbest[v]; //if intersect take second best edge instead
	}
	djikstra(1,gr);
	for(int i=0;i<m;i++)force[1][i]+=dist[edge[i][0]] + c[i];
	/*
	for(int i=0;i<m;i++)cout<<notused[1][i]<<" "; 
	cout<<'\n';
	for(int i=0;i<m;i++)cout<<force[1][i]<<" "; 
	cout<<'\n';
	*/
	ll ans =  min(INF,thonk);
	for(int i=0;i<m;i++)ans = min(ans,min(notused[0][i],force[0][i]) + min(notused[1][i],force[1][i]) + d[i]);
	if(ans == INF)ans = -1;
	cout<<ans;
}

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