#include "shortcut.h"
#include <bits/stdc++.h>
#define MAX 100000000
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(int 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(int 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]));
}
}
int mi=MAX;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
G[i].push_back(ii(j,c));
G[j].push_back(ii(i,c));
fill(dist.begin(),dist.end(),MAX);
bfs(0);
int no=0,ma=-1;
for(int k=0;k<G.size();k++){
if(dist[k]>ma and !G[k].empty()){
no=k;
ma=dist[k];
}
// cout<<"K: "<<k<<" "<<dist[k]<<endl;
}
fill(dist.begin(),dist.end(),MAX);
bfs(no);
for(int k=0;k<G.size();k++){
if(! G[k].empty())
ma=max(dist[k],ma);
}
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:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<l.size();i++){
~^~~~~~~~~
shortcut.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<d.size();i++){
~^~~~~~~~~
shortcut.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<G.size();k++){
~^~~~~~~~~
shortcut.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<G.size();k++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
