제출 #532598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532598		amunduzbaev	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1088 ms	8732 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[3][N];
int a[M], b[M], c[M], p[M];
int d[N], par[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i]>>c[i]>>p[i];
		edges[0][a[i]].push_back({b[i], c[i], i});
		edges[1][b[i]].push_back({a[i], c[i], i});
		edges[2][a[i]].push_back({b[i], c[i], i});
		edges[2][b[i]].push_back({a[i], c[i], i});
	}
	
	auto djk = [&](int t, int u){
		priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> q;
		q.push({0, u});
		for(int i=1;i<=n;i++) d[i] = 2e9;
		memset(par, -1, sizeof par);
		d[u] = 0;
		while(!q.empty()){
			int u = q.top()[1], D = q.top()[0]; q.pop();
			if(D > d[u]) continue;
			for(auto x : edges[t][u]){
				if(d[x[0]] > d[u] + x[1]){
					par[x[0]] = x[2];
					d[x[0]] = d[u] + x[1];
					q.push({d[u] + x[1], x[0]});
				}
			}
		}
		
		vector<int> tt;
		for(int i=1;i<=n;i++){
			if(~par[i]) tt.push_back(par[i]);
		} return tt;
	};
	
	int D = 0;
	vector<int> tot;
	for(int t=0;t<3;t++){
		vector<int> tmp = djk(t, 1);
		tot.insert(tot.end(), tmp.begin(), tmp.end());
		if(!t) D += d[n];
		tmp = djk(t, n);
		tot.insert(tot.end(), tmp.begin(), tmp.end());
		if(!t) D += d[1];
	}
	
	int res = D;
	auto check = [&](int in){
		swap(a[in], b[in]);
		for(int i=1;i<=n;i++) edges[0][i].clear();
		for(int i=0;i<m;i++){
			edges[0][a[i]].push_back({b[i], c[i], i});
		}
		
		int D = 0;
		djk(0, 1);
		D += d[n];
		djk(0, 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++){
		check(i);
		//~ if(is[i]) continue;
		//~ res = min(res, D + p[i]);
	}
	
	if(res >= 2e9) cout<<-1<<"\n";
	else cout<<res<<"\n";
}

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