oj.uz

답안 #125735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125735 2019-07-06T09:45:25 Z abacaba Ceste (COCI17_ceste) C++14
160 / 160
 417 ms 1016 KB 
#include <bits/stdc++.h>
using namespace std;
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
#define int long long
 
struct edge {
	int to, t, c;
	edge(int to, int t, int cost) : to(to), t(t), c(cost) {}
};
 
const int inf = 2e15;
const int N = 2e3 + 15;
int n, m, ans[N];
double d[N];
int sumt[N], sumc[N];
vector <edge> g[N];
bool used[N];
set <pair <double, int> > q;
vector <pair <pii, pii> > edges;
 
void dxtra(double x) {
	fill(d, d + N, inf);
	memset(sumt, 0, sizeof(sumt));
	memset(sumc, 0, sizeof(sumc));
	d[1] = 0;
	q.insert(mp(0, 1));
	while(!q.empty()) {
		int v = q.begin()->se;
		q.erase(q.begin());
		for(auto u : g[v]) {
			if(d[v] + u.t * x + u.c * (1 - x) < d[u.to]) {
				q.erase(mp(d[u.to], u.to));
				sumt[u.to] = sumt[v] + u.t;
				sumc[u.to] = sumc[v] + u.c;
				d[u.to] = d[v] + u.t * x + u.c * (1 - x);
				q.insert(mp(d[u.to], u.to));
			}
		}
	}
	for(int i = 2; i <= n; ++i)
		if(d[i] != inf)
			ans[i] = min(ans[i], sumt[i] * sumc[i]);
}
 
#undef int
 
int main() {
	#define int long long
	fill(ans, ans + N, inf);
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		int u, v, t, c;
		cin >> u >> v >> t >> c;
		g[u].pb(*new edge(v, t, c));
		g[v].pb(*new edge(u, t, c));
		edges.pb({{u, v}, {t, c}});
		edges.pb({{v, u}, {t, c}});
	}
	double x = 0;
    while(1) {
        double new_x = 1;
        dxtra(x);
        for(int i = 0; i < edges.size(); ++i) {
            int v = edges[i].f.f, to = edges[i].f.se, t = edges[i].se.f, c = edges[i].se.se;
            if(d[v] != inf) {
	            int na = sumt[v] + t, nb = sumc[v] + c, ca = sumt[to], cb = sumc[to];
	            double xx = (cb - nb) / (double)(na + cb - nb - ca);
	            if(x < xx && xx <= new_x)
	                new_x = xx;
	        }
        }
        if(x == new_x)
            break;
        x = new_x;
    }
	for(int i = 2; i <= n; ++i)
		cout << (ans[i] == inf ? -1 : ans[i]) << endl;
    return 0;
}

Compilation message

ceste.cpp: In function 'int main()':
ceste.cpp:79:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < edges.size(); ++i) {
                        ~~^~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 808 KB Output is correct
2 Correct 149 ms 816 KB Output is correct
3 Correct 37 ms 760 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 504 KB Output is correct
2 Correct 18 ms 632 KB Output is correct
3 Correct 34 ms 888 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 888 KB Output is correct
2 Correct 182 ms 948 KB Output is correct
3 Correct 287 ms 960 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 888 KB Output is correct
2 Correct 417 ms 1016 KB Output is correct
3 Correct 23 ms 1016 KB Output is correct

Subtask #9
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 936 KB Output is correct
2 Correct 211 ms 888 KB Output is correct
3 Correct 252 ms 1016 KB Output is correct

Subtask #10
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 988 KB Output is correct
2 Correct 238 ms 944 KB Output is correct
3 Correct 262 ms 860 KB Output is correct