#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
lli dis[3][201][201];
vector<ii> al[201];
int p[2][201][201]={};
lli arr[201][201],arr1[201][201],co=0;
lli n,m;
vi ap[2];
lli d1[201][500000];
void floyd(lli t,lli e)
{
for(lli i=1;i<=n;++i)
{
co++;
for(lli j=1;j<=n;++j)
{
arr1[i][j]=arr[i][j];
for(lli k=1;k<=n;++k)
{
arr1[j][k]=min(arr1[j][k],arr[j][i]+arr[i][k]);
}
}
}
swap(arr,arr1);
if(e==n-1)
{
for(lli i=1;i<=n;++i)
for(lli j=1;j<=n;++j)
{
dis[t][i][j]=arr[i][j];
}
}
}
void dij(lli t,lli so,lli te)
{
lli d[201];
int lu[201];
for(lli i=0;i<201;++i)
{
lu[i]=0;
d[i]=10000000000000000;
}
set<ii> s;
s.insert(mp(0,so));
lu[so]=so;
while(s.size()!=0)
{
ii v=(*s.begin());
d[v.S]=v.F;
s.erase(s.begin());
for(lli i=0;i<al[v.S].size();++i)
{
if(d[al[v.S][i].F]>al[v.S][i].S+v.F)
{
s.erase(mp(d[al[v.S][i].F],al[v.S][i].F));
d[al[v.S][i].F]=al[v.S][i].S+v.F;
lu[al[v.S][i].F]=v.S;
s.insert(mp(d[al[v.S][i].F],al[v.S][i].F));
}
}
}
if(lu[te]!=0)
{
int it=n+1;
while(te!=so)
{
if(te==it)
exit(1);
ap[t].pb(te);
p[t][lu[te]][te]=1;
it=te;
te=lu[te];
}
ap[t].pb(so);
}
reverse(all(ap[t]));
}
void set1(int t)
{
for(lli i=1;i<=n;++i)
{
for(lli j=1;j<=n;++j)
{
auto it=(lower_bound(all(al[i]),mp(j,0*1LL)))-al[i].begin();
if(i==j)
arr[i][j]=0;
else
arr[i][j]=10000000000000000;
if(it<al[i].size()&&al[i][it].F==j)
{
arr[i][j]=al[i][it].S;
if(t==1&&p[0][i][j]==1)
{
arr[i][j]=10000000000000000;
it++;
}
if(it<al[i].size()&&al[i][it].F==j)
arr[i][j]=al[i][it].S;
if(t==2&&p[1][i][j]==1)
{
arr[i][j]=10000000000000000;
it++;
}
if(it<al[i].size()&&al[i][it].F==j)
arr[i][j]=al[i][it].S;
}
dis[t][i][j]=10000000000000000;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli test=1;
for(;test>0;--test)
{
cin>>n>>m;
for(lli i=0;i<m;++i)
{
lli f1,s1,w1,k1;
cin>>f1>>s1>>w1>>k1;
al[f1].pb(mp(s1,w1));
d1[f1][int(al[f1].size())-1]=k1;
}
dij(0,1,n);
dij(1,n,1);
set1(0);
floyd(0,n);
set1(1);
floyd(1,n);
set1(2);
floyd(2,1);
lli ans=dis[0][1][n]+dis[0][n][1];
for(lli i=1;i<=n;++i)
{
for(lli j=0;j<al[i].size();++j)
{
lli ans1=dis[0][1][n],ans2=dis[0][n][1];
if(p[0][i][j]!=1)
ans1=min(ans1,al[i][j].S+dis[0][1][al[i][j].F]+dis[0][i][n]);
else
{
ans1=10000000000000000;
for(lli k=0;k<ap[0].size();++k)
{
for(lli l=int(ap[0].size())-1;l>=0;--l)
{
ans1=min(ans1,dis[0][1][ap[0][k]]+dis[1][ap[0][k]][ap[0][l]]+dis[0][ap[0][l]][n]);
if(al[i][j].F==ap[0][l])
break;
}
if(ap[0][k]==i)
break;
}
}
if(p[1][i][j]!=1)
ans2=min(ans2,al[i][j].S+dis[0][n][al[i][j].F]+dis[0][i][1]);
else
{
ans2=10000000000000000;
for(lli k=0;k<ap[1].size()-1;++k)
{
for(lli l=int(ap[1].size())-1;l>=0;--l)
{
ans2=min(ans2,dis[0][n][ap[1][k]]+dis[2][ap[1][k]][ap[1][l]]+dis[0][ap[1][l]][1]);
if(al[i][j].F==ap[1][l])
break;
}
if(ap[1][k]==i)
break;
}
}
ans=min(ans,ans1+ans2+d1[i][j]);
}
}
if(ans>=10000000000000000)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
return(0);
}
Compilation message
ho_t4.cpp: In function 'void dij(lli, lli, lli)':
ho_t4.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lli i=0;i<al[v.S].size();++i)
~^~~~~~~~~~~~~~~
ho_t4.cpp: In function 'void set1(int)':
ho_t4.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(it<al[i].size()&&al[i][it].F==j)
~~^~~~~~~~~~~~~
ho_t4.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(it<al[i].size()&&al[i][it].F==j)
~~^~~~~~~~~~~~~
ho_t4.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(it<al[i].size()&&al[i][it].F==j)
~~^~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lli j=0;j<al[i].size();++j)
~^~~~~~~~~~~~~
ho_t4.cpp:159:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lli k=0;k<ap[0].size();++k)
~^~~~~~~~~~~~~
ho_t4.cpp:176:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lli k=0;k<ap[1].size()-1;++k)
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
6264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
