#pragma GCC optimize("O3","unroll-loops","Ofast")
#include<iostream>
#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}});
while(!kolejka.empty())
{
pair<long long,pair<int,int> > para=kolejka.top();
int x=para.second.first;
kolejka.pop();
if(w[x].od_kogo<-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}});
while(!kolejka.empty())
{
pair<long long,pair<int,int> > para=kolejka.top();
int x=para.second.first;
kolejka.pop();
if(w[x].od_kogo<-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;
cin>>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++)
{
cin>>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)
cout<<"-1";
else cout<<wynik;
return 0;
}
Compilation message
ho_t4.cpp: In function 'void dijkstra(int)':
ho_t4.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0;i<w[x].Q.size();i++)
| ~^~~~~~~~~~~~~~
ho_t4.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0;i<w[x].Q.size();i++)
| ~^~~~~~~~~~~~~~
ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:148:13: warning: unused variable 'pocz' [-Wunused-variable]
148 | int pocz=t[i][3];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
608 KB |
Output is correct |
| 2 |
Correct |
8 ms |
596 KB |
Output is correct |
| 3 |
Correct |
13 ms |
596 KB |
Output is correct |
| 4 |
Correct |
10 ms |
696 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
8 ms |
596 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1812 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1748 KB |
Output is correct |
| 3 |
Correct |
24 ms |
1816 KB |
Output is correct |
| 4 |
Correct |
9 ms |
724 KB |
Output is correct |
| 5 |
Correct |
8 ms |
704 KB |
Output is correct |
| 6 |
Correct |
8 ms |
596 KB |
Output is correct |
| 7 |
Correct |
8 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
35 ms |
1748 KB |
Output is correct |
| 10 |
Correct |
25 ms |
1748 KB |
Output is correct |
| 11 |
Correct |
30 ms |
1804 KB |
Output is correct |
| 12 |
Correct |
25 ms |
1748 KB |
Output is correct |
| 13 |
Correct |
25 ms |
1744 KB |
Output is correct |
| 14 |
Correct |
27 ms |
1828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
596 KB |
Output is correct |
| 3 |
Correct |
25 ms |
1508 KB |
Output is correct |
| 4 |
Correct |
11 ms |
596 KB |
Output is correct |
| 5 |
Correct |
29 ms |
1868 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
608 KB |
Output is correct |
| 2 |
Correct |
8 ms |
596 KB |
Output is correct |
| 3 |
Correct |
13 ms |
596 KB |
Output is correct |
| 4 |
Correct |
10 ms |
696 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
8 ms |
596 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
