Submission #61712

#	Time	Username	Problem	Language	Result	Execution time	Memory
61712		IvanC	Ceste (COCI17_ceste)	C++17	64 / 160	2546 ms	808 KiB

ceste

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<double,int,int,int> informacoes;
typedef tuple<int,int,int> trinca;

const int MAXN = 2010;
const double EPS = 1e-6;

vector<trinca> grafo[MAXN];
int N,M,processado[MAXN];
long long resposta[MAXN];

void dfs(int v){
	if(processado[v]) return;
	processado[v] = 1;
	for(trinca aresta : grafo[v]){
		dfs(get<0>(aresta));
	}
}

ll Dijkstra(int alvo,double alpha,int minimiza_b){
	
	memset(processado,0,sizeof(processado));
	priority_queue<informacoes, vector<informacoes>, greater<informacoes> > pq;
	pq.push({0.0,0,0,1});

	while(!pq.empty()){
		informacoes davez = pq.top();
		pq.pop();
		double dist = get<0>(davez);
		int c1 = get<1>(davez),c2 = get<2>(davez),v = get<3>(davez);
		if(processado[v]) continue;
		processado[v] = 1;
		if(v == alvo){
			//if(alvo == 3) printf("D %.3lf A %.3lf %d %d\n",dist,alpha,c1,c2);
			return 1LL*c1*c2;
		}
		for(trinca aresta : grafo[v]){
			int u = get<0>(aresta),l1 = get<1>(aresta),l2 = get<2>(aresta);
			if(minimiza_b) swap(l1,l2);
			if(!processado[u]) pq.push({dist + (alpha)*l1 + (1.0 - alpha)*l2,c1 + l1,c2 + l2, u});
		}
	}

	return -1;

}

ll checa(int alvo,double alpha){
	return min(Dijkstra(alvo,alpha,0),Dijkstra(alvo,1.0 - alpha,1));
}

int main(){

	cin >> N >> M;
	for(int i = 1;i<=M;i++){
		int u,v,w1,w2;
		cin >> u >> v >> w1 >> w2;
		grafo[u].push_back({v,w1,w2});
		grafo[v].push_back({u,w1,w2});
	}

	dfs(1);
	for(int i = 1;i<=N;i++){
		if(!processado[i]) resposta[i] = -1;
	}

	for(int i = 2;i<=N;i++){
		if(resposta[i] == -1){
			cout << resposta[i] << endl;
			continue;
		}
		long long ans = 1e18;
		double ini = 0.0,fim = 1.0;
		while(fim - ini > EPS){
			double m1 = ini + (fim - ini)/3.0;
			double m2 = fim - (fim - ini)/3.0;
			ll f1 = checa(i,m1);
			ll f2 = checa(i,m2);
			ans = min(ans, min(f1,f2) );
			if(f1 < f2){
				fim = m2 - EPS;
			}
			else{
				ini = m1 + EPS;
			}
		}
		cout << ans << endl;
	}

	return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16