This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#define int long long
using namespace std;
struct wi{
vector<int> Q;
int odw=0;
int kiedy_odw=1e18;
int od_kogo=0;
}*w;
int wynik=1e18;
int kiedy=1;
int n;
int t[60000][4];
int odl[210][210];
map<int,int> nalezy;
void dijkstra(int kto)
{
priority_queue<pair<int,pair<int,int> > > kolejka;
kolejka.push({0,{1,0}});
while(!kolejka.empty())
{
pair<int,pair<int,int> > para=kolejka.top();
int x=para.second.first;
kolejka.pop();
if(w[x].odw==kiedy)
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].odw==kiedy)
continue;
kolejka.push({para.first-koszt,{y,ile}});
}
}
int 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<int,pair<int,int> > para=kolejka.top();
int x=para.second.first;
kolejka.pop();
if(w[x].odw==kiedy)
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].odw==kiedy)
continue;
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;
}
}
int 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],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 (stderr)
ho_t4.cpp:8:1: error: extended character is not valid in an identifier
8 | vector<int> Q;
| ^
ho_t4.cpp:8:1: error: extended character is not valid in an identifier
ho_t4.cpp:8:1: error: extended character is not valid in an identifier
ho_t4.cpp:9:1: error: extended character is not valid in an identifier
9 | int odw=0;
| ^
ho_t4.cpp:9:1: error: extended character is not valid in an identifier
ho_t4.cpp:9:1: error: extended character is not valid in an identifier
ho_t4.cpp:10:1: error: extended character is not valid in an identifier
10 | int kiedy_odw=1e18;
| ^
ho_t4.cpp:10:1: error: extended character is not valid in an identifier
ho_t4.cpp:10:1: error: extended character is not valid in an identifier
ho_t4.cpp:11:1: error: extended character is not valid in an identifier
11 | int od_kogo=0;
| ^
ho_t4.cpp:11:1: error: extended character is not valid in an identifier
ho_t4.cpp:11:1: error: extended character is not valid in an identifier
ho_t4.cpp:21:1: error: extended character is not valid in an identifier
21 | priority_queue<pair<int,pair<int,int> > > kolejka;
| ^
ho_t4.cpp:21:1: error: extended character is not valid in an identifier
ho_t4.cpp:21:1: error: extended character is not valid in an identifier
ho_t4.cpp:22:1: error: extended character is not valid in an identifier
22 | kolejka.push({0,{1,0}});
| ^
ho_t4.cpp:22:1: error: extended character is not valid in an identifier
ho_t4.cpp:22:1: error: extended character is not valid in an identifier
ho_t4.cpp:23:1: error: extended character is not valid in an identifier
23 | while(!kolejka.empty())
| ^
ho_t4.cpp:23:1: error: extended character is not valid in an identifier
ho_t4.cpp:23:1: error: extended character is not valid in an identifier
ho_t4.cpp:24:1: error: extended character is not valid in an identifier
24 | {
| ^
ho_t4.cpp:24:1: error: extended character is not valid in an identifier
ho_t4.cpp:24:1: error: extended character is not valid in an identifier
ho_t4.cpp:25:1: error: extended character is not valid in an identifier
25 | pair<int,pair<int,int> > para=kolejka.top();
| ^
ho_t4.cpp:25:1: error: extended character is not valid in an identifier
ho_t4.cpp:25:1: error: extended character is not valid in an identifier
ho_t4.cpp:25:1: error: extended character is not valid in an identifier
ho_t4.cpp:25:1: error: extended character is not valid in an identifier
ho_t4.cpp:25:1: error: extended character is not valid in an identifier
ho_t4.cpp:25:1: error: extended character is not valid in an identifier
ho_t4.cpp:26:1: error: extended character is not valid in an identifier
26 | int x=para.second.first;
| ^
ho_t4.cpp:26:1: error: extended character is not valid in an identifier
ho_t4.cpp:26:1: error: extended character is not valid in an identifier
ho_t4.cpp:26:1: error: extended character is not valid in an identifier
ho_t4.cpp:26:1: error: extended character is not valid in an identifier
ho_t4.cpp:26:1: error: extended character is not valid in an identifier
ho_t4.cpp:26:1: error: extended character is not valid in an identifier
ho_t4.cpp:27:1: error: extended character is not valid in an identifier
27 | kolejka.pop();
| ^
ho_t4.cpp:27:1: error: extended character is not valid in an identifier
ho_t4.cpp:27:1: error: extended character is not valid in an identifier
ho_t4.cpp:27:1: error: extended character is not valid in an identifier
ho_t4.cpp:27:1: error: extended character is not valid in an identifier
ho_t4.cpp:27:1: error: extended character is not valid in an identifier
ho_t4.cpp:27:1: error: extended character is not valid in an identifier
ho_t4.cpp:28:1: error: extended character is not valid in an identifier
28 | if(w[x].odw==kiedy)
| ^
ho_t4.cpp:28:1: error: extended character is not valid in an identifier
ho_t4.cpp:28:1: error: extended character is not valid in an identifier
ho_t4.cpp:28:1: error: extended character is not valid in an identifier
ho_t4.cpp:28:1: error: extended character is not valid in an identifier
ho_t4.cpp:28:1: error: extended character is not valid in an identifier
ho_t4.cpp:28:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
29 | continue;
| ^
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:29:1: error: extended character is not valid in an identifier
ho_t4.cpp:30:1: error: extended character is not valid in an identifier
30 | w[x].od_kogo=para.second.second;
| ^
ho_t4.cpp:30:1: error: extended character is not valid in an identifier
ho_t4.cpp:30:1: error: extended character is not valid in an identifier
ho_t4.cpp:30:1: error: extended character is not valid in an identifier
ho_t4.cpp:30:1: error: extended character is not valid in an identifier
ho_t4.cpp:30:1: error: extended character is not valid in an identifier
ho_t4.cpp:30:1: error: extended character is not valid in an identifier
ho_t4.cpp:31:1: error: extended character is not valid in an identifier
31 | w[x].odw=kiedy;
| ^
ho_t4.cpp:31:1: error: extended character is not valid in an identifier
ho_t4.cpp:31:1: error: extended character is not valid in an identifier
ho_t4.cpp:31:1: error: extended character is not valid in an identifier
ho_t4.cpp:31:1: error: extended character is not valid in an identifier
ho_t4.cpp:31:1: error: extended character is not valid in an identifier
ho_t4.cpp:31:1: error: extended character is not valid in an identifier
ho_t4.cpp:32:1: error: extended character is not valid in an identifier
32 | w[x].kiedy_odw=-para.first;
| ^
ho_t4.cpp:32:1: error: extended character is not valid in an identifier
ho_t4.cpp:32:1: error: extended character is not valid in an identifier
ho_t4.cpp:32:1: error: extended character is not valid in an identifier
ho_t4.cpp:32:1: error: extended character is not valid in an identifier
ho_t4.cpp:32:1: error: extended character is not valid in an identifier
ho_t4.cpp:32:1: error: extended character is not valid in an identifier
ho_t4.cpp:33:1: error: extended character is not valid in an identifier
33 | for(int i=0;i<w[x].Q.size();i++)
| ^
ho_t4.cpp:33:1: error: extended character is not valid in an identifier
ho_t4.cpp:33:1: error: extended character is not valid in an identifier
ho_t4.cpp:33:1: error: extended character is not valid in an identifier
ho_t4.cpp:33:1: error: extended character is not valid in an identifier
ho_t4.cpp:33:1: error: extended character is not valid in an identifier
ho_t4.cpp:33:1: error: extended character is not valid in an identifier
ho_t4.cpp:34:1: error: extended character is not valid in an identifier
34 | {
| ^
ho_t4.cpp:34:1: error: extended character is not valid in an identifier
ho_t4.cpp:34:1: error: extended character is not valid in an identifier
ho_t4.cpp:34:1: error: extended character is not valid in an identifier
ho_t4.cpp:34:1: error: extended character is not valid in an identifier
ho_t4.cpp:34:1: error: extended character is not valid in an identifier
ho_t4.cpp:34:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
35 | int ile=w[x].Q[i];
| ^
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:35:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
36 | if(ile==kto)
| ^
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:36:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
37 | continue;
| ^
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:37:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
38 | int y;
| ^
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:38:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
39 | if(ile<0)
| ^
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:39:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
40 | y=t[-ile][3];
| ^
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:40:1: error: extended character is not valid in an identifier
ho_t4.cpp:41:1: error: extended character is not valid in an identifier
41 | else y=t[ile][0];
| ^
ho_t4.cpp:41:1: error: extended character is not valid in an identifier
ho_t4.cpp:41:1: error: extended character is not valid in an identifier
ho_t4.cpp:41:1: error: extended character is not valid in an identifier
ho_t4.cpp:41:1: error: extended character is not valid in an identifier
ho_t4.cpp:41:1: error: extended character is not valid in an identifier
ho_t4.cpp:41:1: error: extended character is not valid in an identifier
ho_t4.cpp:41:1: error: extended character