#include "shortcut.h"
#include <bits/stdc++.h>
#define MAX 10000000000
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vi;
vector<vi>G;
int ml;
vector<int>dist(200);
void bfs(int u){
//memset(dist,1000,sizeof (dist));
dist[u]=0;
vector<int>vis(ml,0);
queue<int>q;
q.push(u);
vis[u]=1;
while(!q.empty()){
int v=q.front();
q.pop();
vis[v]=0;
for(int i=0;i<G[v].size();i++){
// cout<<dist[v]<<endl;
if(dist[v]+G[v][i].second<dist[G[v][i].first]){
//cout<<i<<endl;
dist[G[v][i].first]=dist[v]+G[v][i].second;
if(vis[G[v][i].first]==0){
q.push(G[v][i].first);
vis[G[v][i].first]=1;
}
}
}
}
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
ml=n;
G.resize(2*n);
for(long long i=0;i<l.size();i++){
G[i+1].push_back(ii(i,l[i]));
G[i].push_back(ii(i+1,l[i]));
}
for(long long i=0;i<d.size();i++){
if(d[i]!=0){
G[i+n].push_back(ii(i,d[i]));
G[i].push_back(ii(i+n,d[i]));
}
}
long long mi=MAX;
for(long long i=0;i<n;i++){
for(long long j=i+1;j<n;j++){
G[i].push_back(ii(j,c));
G[j].push_back(ii(i,c));
long long ma=-1;
for(long long k=0;k<G.size();k++){
if(!G[k].empty()){
fill(dist.begin(),dist.end(),MAX);
bfs(k);
long long no;
for(long long l=0;l<G.size();l++){
if(dist[l]>ma and !G[l].empty()){
no=k;
ma=dist[l];
}
}
}
}
G[i].pop_back();
G[j].pop_back();
mi=min(mi,ma);
}
}
return mi;
}
Compilation message
shortcut.cpp: In function 'void bfs(int)':
shortcut.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[v].size();i++){
~^~~~~~~~~~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long i=0;i<l.size();i++){
~^~~~~~~~~
shortcut.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long i=0;i<d.size();i++){
~^~~~~~~~~
shortcut.cpp:55:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long k=0;k<G.size();k++){
~^~~~~~~~~
shortcut.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long l=0;l<G.size();l++){
~^~~~~~~~~
shortcut.cpp:59:14: warning: variable 'no' set but not used [-Wunused-but-set-variable]
long long no;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
2 ms |
376 KB |
n = 9, 110 is a correct answer |
| 3 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
