oj.uz

Submission #61711

# Submission time Handle Problem Language Result Execution time Memory
61711 2018-07-26T11:54:39 Z IvanC Ceste (COCI17_ceste) C++17
48 / 160
 2500 ms 768 KB 
#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;
		}
		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;
			if(checa(i,m1) < checa(i,m2)){
				fim = m2 - EPS;
			}
			else{
				ini = m1 + EPS;
			}
		}
		cout << checa(i,ini) << endl;
	}

	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 376 KB Output isn't correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 440 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 488 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2560 ms 672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2592 ms 720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2559 ms 744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2531 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2539 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -