Submission #534860

#	Time	Username	Problem	Language	Result	Execution time	Memory
534860		amunduzbaev	Olympic Bus (JOI20_ho_t4)	C++17	11 / 100	34 ms	5516 KiB

ho_t4

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
 
const int N = 205, M = 5e4 + 5;
vector<ar<int, 3>> edges[N];
int a[M], b[M], c[M], p[M];
int d[N], par[N], T[N][N], used[N];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			T[i][j] = 1e10;
		} T[i][i] = 0;
	}
	
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i]>>c[i]>>p[i];
		edges[a[i]].push_back({b[i], c[i], i});
		T[a[i]][b[i]] = min(T[a[i]][b[i]], c[i]);
	}
	
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				T[i][j] = min(T[i][j], T[i][k] + T[k][j]);
			}
		}
	}
	
	vector<int> tot;
	auto djk = [&](int u){
		for(int i=1;i<=n;i++) d[i] = 1e10;
		memset(par, -1, sizeof par);
		memset(used, 0, sizeof used);
		d[u] = 0;
		
		while(~u){
			used[u] = 1;
			int p = -1;
			for(auto x : edges[u]){
				if(d[x[0]] > d[u] + x[1]){
					d[x[0]] = d[u] + x[1];
					par[x[0]] = x[2];
				}
			}
			
			for(int i=1;i<=n;i++){
				if(used[i]) continue;
				if(p == -1 || d[i] < d[p]) p = i;
			}
			
			u = p;
		}
		
		for(int i=1;i<=n;i++){
			if(~par[i]) tot.push_back(par[i]);
		}
	};
	
	//~ const int inf = 2e9;
	//~ auto bashka = [&](int t, int u){
		//~ priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> q;
		//~ q.push({0, u});
		//~ vector<ar<int, 2>> d(n + 1, {inf, inf});
		//~ memset(par, -1, sizeof par);
		//~ d[u][0] = 0;
		//~ while(!q.empty()){
			//~ int u = q.top()[1], D = q.top()[0]; q.pop();
			//~ if(u <= n){
				//~ if(D > d[u][0]) continue;
				//~ for(auto x : edges[t][u]){
					//~ if(d[x[0]][0] > d[u][0] + x[1]){
						//~ d[x[0]][0] = d[u][0] + x[1];
						//~ q.push({d[x[0]][0], x[0]});
					//~ }
				//~ }
				
				//~ for(auto x : edges[t^1][u]){
					//~ if(d[x[0]][1] > d[u][0] + x[1]){
						//~ d[x[0]][1] = d[u][0] + x[1];
						//~ q.push({d[x[0]][1], x[0] + n});
					//~ }
				//~ }
			//~ } else {
				
			//~ }
		//~ }
		
		//~ vector<int> tt;
		//~ for(int i=1;i<=n;i++){
			//~ if(~par[i]) tt.push_back(par[i]);
		//~ } return tt;
	//~ };
	
	ar<int, 2> D {};
	djk(1), D[0] = d[n];
	djk(n), D[1] = d[1];
	
	int res = D[0] + D[1];
	auto check = [&](int in){
		swap(a[in], b[in]);
		for(int i=1;i<=n;i++) edges[i].clear();
		for(int i=0;i<m;i++){
			edges[a[i]].push_back({b[i], c[i], -1});
		}
		
		int D = 0;
		djk(1), D += d[n];
		djk(n), D += d[1];
		res = min(res, D + p[in]);
		swap(a[in], b[in]);
	};
	
	sort(tot.begin(), tot.end());
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	for(int i=0;i<m;i++){
		int st = min(T[1][b[i]] + T[a[i]][n] + c[i], D[0]), ts = min(T[n][b[i]] + c[i] + T[a[i]][1], D[1]);
		res = min(res, st + ts + p[i]);
	}
	
	if(res >= 1e10) cout<<-1<<"\n";
	else cout<<res<<"\n";
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:106:7: warning: variable 'check' set but not used [-Wunused-but-set-variable]
  106 |  auto check = [&](int in){
      |       ^~~~~

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