oj.uz

Submission #61712

# Submission time Handle Problem Language Result Execution time Memory
61712 2018-07-26T11:56:08 Z IvanC Ceste (COCI17_ceste) C++17
64 / 160
 2500 ms 808 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;
		}
		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.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 540 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 540 KB Output is correct

Subtask #5
0 / 16.0

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

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 616 KB Output is correct
2 Incorrect 292 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2528 ms 736 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 2534 ms 788 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 2534 ms 808 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 2544 ms 808 KB Time limit exceeded
2 Halted 0 ms 0 KB -