#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];
lli n,m;
vi ap[2];
void floyd(lli t,lli e)
{
if(e>1)
floyd(t,e-1);
for(lli i=1;i<=n;++i)
{
for(lli j=1;j<=n;++j)
{
arr1[i][j]=arr[i][j];
for(lli k=0;k<al[i].size();++k)
{
if(t==1&&p[0][i][k]==1)
continue;
if(t==2&&p[1][i][k]==1)
continue;
arr1[i][j]=min(arr1[i][j],al[i][k].S+arr[al[i][k].F][j]);
}
}
}
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];
ii lu[201];
for(lli i=0;i<201;++i)
{
lu[i]=mp(0,0);
d[i]=1000000000000000000;
}
set<ii> s;
s.insert(mp(0,so));
lu[so]=mp(so,0);
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]=mp(v.S,i);
s.insert(mp(d[al[v.S][i].F],al[v.S][i].F));
}
}
}
if(lu[te].F!=0)
{
while(te!=so)
{
ap[t].pb(te);
p[t][lu[te].F][lu[te].S]=1;
te=lu[te].F;
}
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)
{
if(i==j)
arr[i][j]=0;
else
arr[i][j]=1000000000000000000;
dis[t][i][j]=1000000000000000000;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli test=1;
memset(dis,-1,sizeof(dis));
for(;test>0;--test)
{
cin>>n>>m;
lli d[n][n];
for(lli i=0;i<m;++i)
{
lli f,s,w,k;
cin>>f>>s>>w>>k;
al[f].pb(mp(s,w));
d[f][s]=k;
}
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=1000000000000000000;
for(lli k=0;k<=n-1;++k)
{
for(lli l=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=1000000000000000000;
for(lli k=0;k<=n-1;++k)
{
for(lli l=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+d[i][al[i][j].F]);
}
}
if(ans>=1000000000000000000)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
return(0);
}
Compilation message
ho_t4.cpp: In function 'void floyd(lli, lli)':
ho_t4.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lli k=0;k<al[i].size();++k)
~^~~~~~~~~~~~~
ho_t4.cpp: In function 'void dij(lli, lli, lli)':
ho_t4.cpp:67: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 'int main()':
ho_t4.cpp:132:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lli j=0;j<al[i].size();++j)
~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
224 ms |
2552 KB |
Output is correct |
| 2 |
Correct |
82 ms |
2304 KB |
Output is correct |
| 3 |
Correct |
233 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
236 ms |
2304 KB |
Output is correct |
| 5 |
Runtime error |
19 ms |
3916 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1089 ms |
4600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
233 ms |
2304 KB |
Output is correct |
| 2 |
Correct |
80 ms |
2304 KB |
Output is correct |
| 3 |
Execution timed out |
1088 ms |
3832 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
224 ms |
2552 KB |
Output is correct |
| 2 |
Correct |
82 ms |
2304 KB |
Output is correct |
| 3 |
Correct |
233 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
236 ms |
2304 KB |
Output is correct |
| 5 |
Runtime error |
19 ms |
3916 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
