Submission #532615

#	Time	Username	Problem	Language	Result	Execution time	Memory
532615		amunduzbaev	Fire (JOI20_ho_t5)	C++17	0 / 100	14 ms	7388 KiB

ho_t5

#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]);
		}
	};

	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());
	vector<int> is(m);
	for(auto x : tot){
		check(x);
		is[x] = 1;
	}
	
	for(int i=0;i<m;i++){
		if(is[i]) continue;
		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";
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80