| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 757200 | groshi | Olympic Bus (JOI20_ho_t4) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3","unroll-loops","Ofast")
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
struct wi{
vector<int> Q;
int odw=0;
long long kiedy_odw=1e18;
int od_kogo=0;
}*w;
long long wynik=1e18;
int kiedy=1;
int n;
int t[60000][4];
long long odl[210][210];
map<int,int> nalezy;
void dijkstra(int kto)
{
priority_queue<pair<long long,pair<int,int> > > kolejka;
kolejka.push({0,{1,0}});
for(int i=1;i<=n;i++)
w[i].kiedy_odw=1e18;
while(!kolejka.empty())
{
pair<long long,pair<int,int> > para=kolejka.top();
int x=para.second.first;
kolejka.pop();
if(w[x].kiedy_odw<-para.first)
continue;
w[x].od_kogo=para.second.second;
w[x].odw=kiedy;
w[x].kiedy_odw=-para.first;
for(int i=0;i<w[x].Q.size();i++)
{
int ile=w[x].Q[i];
if(ile==kto)
continue;
int y;
if(ile<0)
y=t[-ile][3];
else y=t[ile][0];
int koszt=t[abs(ile)][1];
if(w[y].kiedy_odw<=-para.first+koszt)
continue;
w[y].kiedy_odw=-para.first+koszt;
kolejka.push({para.first-koszt,{y,ile}});
}
}
long long d1=w[n].kiedy_odw;
bool git1=0,git2=0;
if(w[n].odw==kiedy)
git1=1;
if(kto==0 && w[n].odw==kiedy)
{
int jestem=n;
while(jestem!=1)
{
nalezy[w[jestem].od_kogo]=1;
int x,y;
x=t[w[jestem].od_kogo][0];
y=t[w[jestem].od_kogo][3];
if(x==jestem)
jestem=y;
else jestem=x;
}
}
kiedy++;
kolejka.push({0,{n,0}});
for(int i=1;i<=n;i++)
w[i].kiedy_odw=1e18;
while(!kolejka.empty())
{
pair<long long,pair<int,int> > para=kolejka.top();
int x=para.second.first;
kolejka.pop();
if(w[x].kiedy_odw<-para.first)
continue;
w[x].od_kogo=para.second.second;
w[x].odw=kiedy;
w[x].kiedy_odw=-para.first;
for(int i=0;i<w[x].Q.size();i++)
{
int ile=w[x].Q[i];
if(ile==kto)
continue;
int y;
if(ile<0)
y=t[-ile][3];
else y=t[ile][0];
int koszt=t[abs(ile)][1];
if(w[y].kiedy_odw<=-para.first+koszt)
continue;
w[y].kiedy_odw=-para.first+koszt;
kolejka.push({para.first-koszt,{y,ile}});
}
}
if(w[1].odw==kiedy)
git2=1;
if(kto==0 && w[1].odw==kiedy)
{
int jestem=1;
while(jestem!=n)
{
nalezy[w[jestem].od_kogo]=1;
int x,y;
x=t[w[jestem].od_kogo][0];
y=t[w[jestem].od_kogo][3];
if(x==jestem)
jestem=y;
else jestem=x;
}
}
long long d2=w[1].kiedy_odw;
if(git1==1 && git2==1)
wynik=min(wynik,d1+d2+t[kto][2]);
}
int32_t main()
{
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
int m,x,y,a,b;
scanf("%i %i",&n,&m);
w=new wi[n+3];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
odl[i][j]=1e18;
for(int i=1;i<=m;i++)
{
scanf("%i %i %i %i",&x,&y,&a,&b);
w[x].Q.push_back(i);
t[i][0]=y;
t[i][1]=a;
t[i][2]=b;
t[i][3]=x;
odl[x][y]=min(odl[x][y],(long long)a);
}
for(int i=1;i<=n;i++)
odl[i][i]=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
odl[i][j]=min(odl[i][j],odl[i][k]+odl[k][j]);
dijkstra(0);
kiedy++;
for(auto it=nalezy.begin();it!=nalezy.end();it++)
{
int i=it->first;
int odwr=t[i][0];
int pocz=t[i][3];
w[odwr].Q.push_back(-i);
dijkstra(i);
kiedy++;
w[odwr].Q.pop_back();
}
wynik=min(wynik,odl[n][1]+odl[1][n]);
for(int i=1;i<=m;i++)
{
if(nalezy.find(i)!=nalezy.end())
continue;
int x=t[i][3];
int y=t[i][0];
int odwr=t[i][2];
int koszt=t[i][1];
wynik=min(wynik,odl[1][n]+odl[n][y]+odl[x][1]+odwr+koszt);
wynik=min(wynik,odl[n][1]+odl[x][n]+odl[1][y]+odwr+koszt);
wynik=min(wynik,odl[1][y]+odl[x][n]+odl[n][y]+odl[x][1]+odwr+2*koszt);
}
if(wynik>=1e18)
printf("-1");
else printf("%i",wynik);
return 0;
}