oj.uz

답안 #239657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239657 2020-06-17T05:51:46 Z MrRobot_28 Ceste (COCI17_ceste) C++17
160 / 160
 285 ms 892 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct edge{
	int a, b, t, c;
	edge(int a, int b, int t, int c):
		a(a),
		b(b),
		t(t),
		c(c){};
};
vector <edge> edges;
vector<double> dist;
vector <int> ans, best;
vector <int> sum_a, sum_b;
vector <vector <int> > g;
int n;
void build_path(double x)
{
	for(int i = 0; i < dist.size(); i++)
	{
		dist[i] = 1e18;
	}
	dist[0] = 0;
	priority_queue <pair <double, int> > q;
	q.push({0, 0});
	while(q.size() != 0)
	{
		int v = q.top().second;
		q.pop();
		for(int i = 0; i < g[v].size(); i++)
		{
			int to = edges[g[v][i]].b;
			double t = edges[g[v][i]].t;
			double c = edges[g[v][i]].c;
			if(dist[to] > dist[v] + x * t + (1 - x) * c){
				dist[to] = dist[v] + x * t + (1 - x) * c;
				sum_a[to] = sum_a[v] + t;
				sum_b[to] = sum_b[v] + c;
				q.push({-dist[to], to});
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(dist[i] < 1e18 / 2)
		{
			best[i] = min(best[i], sum_a[i] * sum_b[i]);
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int m;
	cin >> n >> m;
	dist.resize(n, 1e18);
	best.resize(n, 1e18);
	sum_a.resize(n);
	sum_b.resize(n);
	g.resize(n);
	for(int i = 0; i < m; i++)
	{
		int a, b, t, c;
		cin >> a >> b >> t >> c;
		a--;
		b--;
		edges.push_back(edge(a, b, t, c));
		g[a].push_back(edges.size() - 1);
		edges.push_back(edge(b, a, t, c));
		g[b].push_back(edges.size() - 1);
	}
	double x = 0;
	while(true)
	{
		build_path(x);
		double new_x = 1;
		for(int i = 0; i < edges.size(); i++)
		{
			int v = edges[i].a;
			int to = edges[i].b;
			int t = edges[i].t;
			int c = edges[i].c;
			if(best[v] == 1e18)
			{
				continue;
			}
			int new_path_a = sum_a[v] + t;
			int new_path_b = sum_b[v] + c;
			int cur_path_a = sum_a[to];
			int cur_path_b = sum_b[to];
			new_path_a -= new_path_b;
			cur_path_a -= cur_path_b;
			double pos = (cur_path_b - new_path_b) / (double) (new_path_a - cur_path_a);
			if(x < pos && new_x >= pos)
			{
				new_x = pos;
			}
		}
		if(new_x == x)
		{
			break;
		}
		x = new_x;
	}
	for(int i = 1; i < n; i++)
	{
		if(best[i] == 1e18)
		{
			best[i] = -1;
		}
		cout << best[i] << "\n";
	}
    return 0;
}

Compilation message

ceste.cpp: In function 'void build_path(double)':
ceste.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < dist.size(); i++)
                 ~~^~~~~~~~~~~~~
ceste.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
ceste.cpp: In function 'int main()':
ceste.cpp:80:20: 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 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 640 KB Output is correct
2 Correct 108 ms 640 KB Output is correct
3 Correct 35 ms 760 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 476 KB Output is correct
2 Correct 17 ms 512 KB Output is correct
3 Correct 41 ms 640 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 768 KB Output is correct
2 Correct 149 ms 640 KB Output is correct
3 Correct 207 ms 640 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 888 KB Output is correct
2 Correct 285 ms 640 KB Output is correct
3 Correct 16 ms 640 KB Output is correct

Subtask #9
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 864 KB Output is correct
2 Correct 147 ms 892 KB Output is correct
3 Correct 164 ms 768 KB Output is correct

Subtask #10
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 768 KB Output is correct
2 Correct 159 ms 888 KB Output is correct
3 Correct 178 ms 768 KB Output is correct