Submission #239657

#	Time	Username	Problem	Language	Result	Execution time	Memory
239657		MrRobot_28	Ceste (COCI17_ceste)	C++17	160 / 160	285 ms	892 KiB

ceste

#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 (stderr)

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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16