#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<long long>dist(2000);
void bfs(int u){
dist[u]=0;
vector<int>vis(ml,0);
queue<int>q;
q.push(u);
vis[u]=1;
while(!q.empty()){
int v=q.front();
//cout<<v<<endl;
q.pop();
vis[v]=0;
for(int i=0;i<G[v].size();i++){
long long x=G[v][i].first;
long long w=G[v][i].second;
if(dist[v]+w<dist[x]){
dist[x]=dist[v]+w;
if(vis[x]==0){
q.push(x);
vis[x]=1;
}
}
}
}
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
ml=2*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(int k=0;k<G.size();k++){
fill(dist.begin(),dist.end(),MAX);
//cout<<"0:"<<endl;
bfs(k);
for(int l=0;l<G.size();l++){
if(!G[l].empty()){
ma=max(ma,dist[l]);
}
}
}
/*
vector<long long> no;
for(int k=0;k<G.size();k++){
if(ma<=dist[k] and !G[k].empty()){
ma=dist[k];
no.push_back(k);
}
}
for(int k=0;k<no.size();k++){
fill(dist.begin(),dist.end(),MAX);
bfs(no[k]);
for(int l=0;l<G.size();l++){
if(!G[l].empty()){
long long w=dist[l];
ma=max(ma,w);
}
}
}*/
G[i].pop_back();
G[j].pop_back();
if(mi>ma){
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:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<G.size();k++){
~^~~~~~~~~
shortcut.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int l=0;l<G.size();l++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
372 KB |
n = 4, incorrect answer: jury 80 vs contestant 10000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
