제출 #61710

#제출 시각아이디문제언어결과실행 시간메모리
61710IvanCCeste (COCI17_ceste)C++17
16 / 160
2553 ms1276 KiB
#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-3; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...