#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n = N; int m = M; int l = L;
vector<vector<int>> adj(n, vector<int>());
vector<vector<int>> dma(n, vector<int>());
vector<int> a(A, A+m);
vector<int> b(B,B+m);
vector<int> t(T, T+m);
for(int i = 0; i < a.size(); i ++){
adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]);
dma[a[i]].push_back(t[i]); dma[b[i]].push_back(t[i]);
}
vector<int> components = {0};
queue<int> q0; q0.push(0);
vector<int> v(n, 0);
int node = 0;
while(!q0.empty()){
node = q0.front();
q0.pop();
if(!v[node]){
v[node] = 1;
for(int i = 0; i < adj[node].size(); i ++){
q0.push(adj[node][i]);
}
}
if(q0.empty()){
for(int i = 0; i < v.size(); i ++){
if(v[i] == 0){
components.push_back(i);
q0.push(i);
break;
}
}
}
}
queue<int> q;
vector<int> d0(n, INT_MAX / 2);
vector<int> v0(n, 0);
vector<int> d(n, INT_MAX / 2);
vector<int> visited(n, 0);
vector<pair<int, int>> prefix0;
vector<pair<int, int>> prefix;
vector<int> csize;
//cout << components.size() << " ";
for(int x = 0; x < components.size(); x ++){
prefix = prefix0;
int furtherest = 0; int dist = 0;
d = d0; visited = v0;
d[components[x]] = 0;
// Finds the furtherest node in the component
q.push(components[x]);
while(!q.empty()){
node = q.front();
q.pop();
if(!visited[node]){
visited[node] = 1;
for(int i = 0; i < adj[node].size(); i ++){
q.push(adj[node][i]);
d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]);
}
}
}
for(int i = 0; i < visited.size(); i ++){
if(visited[i]){
if(d[i] >= dist){
dist = d[i];
furtherest = i;
}
}
}
// Generate a prefix array of nodes
d = d0; visited = v0;
d[furtherest] = 0;
// Finds the furtherest node in the component
q.push(furtherest);
//cout << furtherest << "\n";
while(!q.empty()){
node = q.front();
q.pop();
if(!visited[node]){
visited[node] = 1;
for(int i = 0; i < adj[node].size(); i ++){
q.push(adj[node][i]);
//cout << d[node] << " ";
d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]);
}
}
}
for(int i = 0; i < visited.size(); i ++){
if(visited[i]){
// DISTANCE THEN NODE
prefix.push_back({d[i], i});
//cout << d[i] << " ";
}
}
//cout << "\n";
sort(prefix.begin(), prefix.end());
//cout << components[x] << " | ";
int maxd = prefix[prefix.size() - 1].first;
int score = INT_MAX / 2;
int best = 0;
for(int i = 0; i < prefix.size(); i ++){
//cout << prefix[i].first << " ";
if(abs(maxd / 2 - prefix[i].first) < score){
score = abs(maxd / 2 - prefix[i].first);
best = max(prefix[i].first, maxd - prefix[i].first);
}
}
csize.push_back(best);
//cout << best << "\n";
//cout << furtherest << " " << dist << " " << components[i] << "\n";
//cout << components[i] << " ";
}
return csize[0] + csize[1] + l;
}
/*
g++ -DEVAL -static -O2 -o dreaming grader.cpp dreaming.cpp
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i = 0; i < a.size(); i ++){
| ~~^~~~~~~~~~
dreaming.cpp:26:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i = 0; i < adj[node].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < v.size(); i ++){
| ~~^~~~~~~~~~
dreaming.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int x = 0; x < components.size(); x ++){
| ~~^~~~~~~~~~~~~~~~~~~
dreaming.cpp:61:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < adj[node].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < visited.size(); i ++){
| ~~^~~~~~~~~~~~~~~~
dreaming.cpp:89:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0; i < adj[node].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i < visited.size(); i ++){
| ~~^~~~~~~~~~~~~~~~
dreaming.cpp:110:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i = 0; i < prefix.size(); i ++){
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
96 ms |
16552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
96 ms |
16552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1059 ms |
10644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
96 ms |
16552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
