| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 239657 |
2020-06-17T05:51:46 Z |
MrRobot_28 |
Ceste (COCI17_ceste) |
C++17 |
|
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++)
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
