| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1181143 | Szymon_Pilipczuk | Olympic Bus (JOI20_ho_t4) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int k[50000][4];
ll inf = 1e12;
ll dis[4][200];
vector<int> dis3[4][200];
map<vector<int>,int> kr;
vector<vector<vector<int>>> gr[2];
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
void dk(int v,int c,int p)
{
for(vector<int> i : gr[p%2][v])
{
if(dis[p][i[0]] > c+i[1])
{
pq.push({c+i[1],i[0],p});
dis[p][i[0]] = i[1]+c;
if(p%2 == 0)
{
dis3[p][i[0]] = {v,i[0],i[1],i[2]};
}
else
{
dis3[p][i[0]] = {i[0],v,i[1],i[2]};
}
}
}
}
ll dis2[200];
void dk2(int c,int v)
{
for(vector<int> i : gr[0][v])
{
if(dis2[i[0]] > c+i[1])
{
pq.push({c+i[1],i[0]});
dis2[i[0]] = c+i[1];
}
}
}
void del()
{
for(int i = 0;i<n;i++)
{
dis2[i] = inf;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
gr[0].resize(n);
gr[1].resize(n);
for(int i = 0;i<4;i++)
{
for(int j = 0;j<n;j++)
{
dis[i][j] = inf;
}
}
for(int i = 0;i<m;i++)
{
int u,v,c,d;
cin>>u>>v>>c>>d;
u--;v--;
kr[{u,v,c,d}] = i;
gr[0][u].push_back({v,c,d});
gr[1][v].push_back({u,c,d});
k[i][0] = u;
k[i][1] = v;
k[i][2] = c;
k[i][3] = d;
}
pq.push({0,0,0});
pq.push({0,0,1});
pq.push({0,n-1,2});
pq.push({0,n-1,3});
dis[0][0]= 0;
dis[1][0] = 0;
dis[2][n-1] = 0;
dis[3][n-1] = 0;
while(!pq.empty())
{
int a,b,c;
a = pq.top()[1];
b = pq.top()[0];
c = pq.top()[2];
pq.pop();
if(dis[c][a] == b)
{
dk(a,b,c);
}
}
unordered_set<int> sps;
for(int i = 0;i<2;i++)
{
for(int j = 1;j<n;j++)
{
if(dis3[i][j].size() != 0)
{
sps.insert(kr[dis3[i][j]]);
}
}
}
for(int i = 2;i<4;i++)
{
for(int j = 0;j<n-1;j++)
{
if(dis3[i][j].size() != 0)
{
sps.insert(kr[dis3[i][j]]);
}
}
}
ll ans = dis[0][n-1]+dis[2][0];
dis[2][n-1] = 0;
dis[3][n-1] = 0;
dis[0][0] = 0;
dis[1][0] = 0;
for(int i = 0;i<m;i++)
{
if(sps.find(i) == sps.end())
{
ans = min(ans,(ll)k[i][3]+min(dis[0][n-1],dis[0][k[i][1]]+k[i][2]+dis[3][k[i][0]])+min(dis[2][0],dis[2][k[i][1]]+k[i][2]+dis[1][k[i][0]]));
}
}
del();
for(int i = 0;i<n;i++)
{
for(int j : gr[0][i])
{
if(sps.find(kr[{i,j[0],j[1],j[2]}]) != sps.end())
{
int cu = j[0];
ll cans = j[2];
j[0] = i;
gr[0][cu].push_back({i,j[1]});
pq.push({0,0});
dis2[0] = 0;
while(!pq.empty())
{
int a = pq.top()[0],b = pq.top()[1];
pq.pop();
if(dis2[b] == a)
{
dk2(a,b);
}
}
cans += dis2[n-1];
del();
pq.push({0,n-1});
dis2[n-1] =0 ;
while(!pq.empty())
{
int a = pq.top()[0],b = pq.top()[1];
pq.pop();
if(dis2[b]== a)
{
dk2(a,b);
}
}
cans+=dis2[0];
del();
j[0] = cu;
gr[0][cu].pop_back();
ans = min(ans,cans);
}
}
}
if(ans >= inf)
{
cout<<-1<<"\n";
}
else
{
cout<<ans<<"\n";
}
}