#include "shortcut.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,jar[550],tam[550],has,j,d[550],C,b[550];
vector<ll> v[550],w[550];
ll cak(ll aa)
{
ll ii;
priority_queue<pair<ll,ll> > pq;
for(ii=0;ii<(n*2);ii++)
b[ii]=0;
for(ii=0;ii<(n*2);ii++)
d[ii]=1e18;
d[aa]=0;
ll ma=0;
pq.push(mp(0,aa));
while(!pq.empty())
{
ll u=pq.top().se;
ll dis=-pq.top().fi;
pq.pop();
if(b[u])
continue;
b[u]=1;
//cout<<aa<<" "<<bb<<" "<<u<<" "<<dis<<" "<<d[u]<<"\n";
ma=max(ma,d[u]);
for(ii=0;ii<v[u].size();ii++)
{
if(d[v[u][ii]]>d[u]+w[u][ii])
{
d[v[u][ii]]=d[u]+w[u][ii];
pq.push(mp(-d[v[u][ii]],v[u][ii]));
}
}
}
return ma;
}
ll cek(ll aa,ll bb)
{
ll ii;
v[aa].pb(bb);
w[aa].pb(C);
v[bb].pb(aa);
w[bb].pb(C);
ll ma=0,cln=0;
for(ii=n;ii<n*2;ii++)
ma=max(ma,cak(ii));
v[aa].pop_back();
w[aa].pop_back();
v[bb].pop_back();
w[bb].pop_back();
return ma;
//cout<<aa<<" "<<bb<<" "<<ma<<" "<<cln<<"\n";
/*
ma=0;
for(ii=0;ii<(n*2);ii++)
d[ii]=1e18;
d[cln]=0;
pq.push(mp(0,cln));
cln=0;
while(!pq.empty())
{
ll u=pq.top().se;
ll dis=-pq.top().fi;
pq.pop();
if(d[u]!=dis)
continue;
ma=max(ma,d[u]);
if(ma==d[u])
cln=u;
ll ii;
for(ii=0;ii<v[u].size();ii++)
{
if(d[v[u][ii]]>d[u]+w[u][ii])
{
d[v[u][ii]]=d[u]+w[u][ii];
pq.push(mp(-d[v[u][ii]],v[u][ii]));
}
}
}
//cout<<aa<<" "<<bb<<" "<<ma<<"\n";
//cout<<ma<<"\n";
return ma;
*/
}
long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int c)
{
n=N;
C=c;
for(i=0;i<(n*2);i++)
{
v[i].clear();
w[i].clear();
}
for(i=0;i<(n-1);i++)
{
v[i].pb(i+1);
w[i].pb(jar[i]);
v[i+1].pb(i);
w[i+1].pb(jar[i]);
}
for(i=0;i<n;i++)
{
v[i].pb(i+n);
w[i].pb(tam[i]);
v[i+n].pb(i);
w[i+n].pb(tam[i]);
}
for(i=0;i<(n-1);i++)
jar[i]=l[i];
for(i=0;i<n;i++)
tam[i]=d[i];
has=1e18;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
has=min(has,cek(i,j));
return has;
}
Compilation message
shortcut.cpp: In function 'll cak(ll)':
shortcut.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[u].size();ii++)
~~^~~~~~~~~~~~
shortcut.cpp:25:6: warning: unused variable 'dis' [-Wunused-variable]
ll dis=-pq.top().fi;
^~~
shortcut.cpp: In function 'll cek(ll, ll)':
shortcut.cpp:50:10: warning: unused variable 'cln' [-Wunused-variable]
ll ma=0,cln=0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
