#include <bits/stdc++.h>
using namespace std;
long long inf = (long long)1000000000*1000000000;
long long dis[4][200][2];
map<vector<long long>,int> kr;
vector<vector<vector<long long>>> gr[2];
priority_queue<vector<long long>> pq;
void dk(long long v,long long c,long long p,long long p2)
{
for(int i = 0;i<gr[p2][v].size();i++)
{
if(dis[p][gr[p2][v][i][0]][0] > c+gr[p2][v][i][1])
{
pq.push({-1*(c+gr[p2][v][i][1]),gr[p2][v][i][0],p,p2});
dis[p][gr[p2][v][i][0]][0] = gr[p2][v][i][1]+c;
if(p2 == 0)
{
dis[p][gr[p2][v][i][0]][1] = kr[{v,gr[p2][v][i][0],gr[p2][v][i][1],gr[p2][v][i][2]}];
}
else
{
dis[p][gr[p2][v][i][0]][1] = kr[{gr[p2][v][i][0],v,gr[p2][v][i][1],gr[p2][v][i][2]}];
}
}
}
}
priority_queue<vector<long long>> pq2;
long long dis2[200];
void dk2(long long v,long long c)
{
for(int i = 0;i<gr[0][v].size();i++)
{
if(dis2[gr[0][v][i][0]] > c+gr[0][v][i][1])
{
pq2.push({-1*(c+gr[0][v][i][1]),gr[0][v][i][0]});
dis2[gr[0][v][i][0]] = c+gr[0][v][i][1];
}
}
}
void del()
{
for(int i = 0;i<200;i++)
{
dis2[i] = inf;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
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][0] = inf;
dis[i][j][1] = -1;
}
}
int k[m][4];
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,0});
pq.push({0,0,1,1});
pq.push({0,n-1,2,0});
pq.push({0,n-1,3,1});
while(!pq.empty())
{
long long a,b,c,d;
a = pq.top()[1];
b = pq.top()[0]*-1;
c = pq.top()[2];
d = pq.top()[3];
pq.pop();
dk(a,b,c,d);
}
set<int> sps;
vector<int> sp;
for(int i = 0;i<2;i++)
{
for(int j = 1;j<n;j++)
{
if(dis[i][j][1] != -1)
{
sp.push_back(dis[i][j][1]);
sps.insert(dis[i][j][1]);
}
}
}
for(int i = 2;i<4;i++)
{
for(int j = 0;j<n-1;j++)
{
if(dis[i][j][1] != -1)
{
sp.push_back(dis[i][j][1]);
sps.insert(dis[i][j][1]);
}
}
}
long long ans = dis[0][n-1][0]+dis[2][0][0];
for(int i = 0;i<m;i++)
{
if(sps.find(i) == sps.end())
{
ans = min(ans,k[i][3]+min(dis[0][n-1][0],dis[0][k[i][1]][0]+k[i][2]+dis[3][k[i][0]][0])+min(dis[2][0][0],dis[2][k[i][1]][0]+k[i][2]+dis[1][k[i][0]][0]));
}
}
del();
for(int i = 0;i<n;i++)
{
for(int j = 0;j<gr[0][i].size();j++)
{
if(sps.find(kr[{i,gr[0][i][j][0],gr[0][i][j][1],gr[0][i][j][2]}]) != sps.end())
{
int cu = gr[0][i][j][0];
long long cans = gr[0][i][j][2];
gr[0][i][j][0] = i;
gr[0][cu].push_back({i,gr[0][i][j][1]});
pq2.push({0,0});
while(!pq2.empty())
{
long long a = pq2.top()[1],b = pq2.top()[0]*-1;
pq2.pop();
dk2(a,b);
}
cans += dis2[n-1];
del();
pq2.push({0,n-1});
while(!pq2.empty())
{
long long a = pq2.top()[1],b = pq2.top()[0]*-1;
pq2.pop();
dk2(a,b);
}
cans+=dis2[0];
del();
gr[0][i][j][0] = cu;
gr[0][cu].pop_back();
ans = min(ans,cans);
}
}
}
if(ans >= inf)
{
cout<<-1;
}
else
{
cout<<ans;
}
}
Compilation message
ho_t4.cpp: In function 'void dk(long long int, long long int, long long int, long long int)':
ho_t4.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i = 0;i<gr[p2][v].size();i++)
| ~^~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'void dk2(long long int, long long int)':
ho_t4.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = 0;i<gr[0][v].size();i++)
| ~^~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:128:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int j = 0;j<gr[0][i].size();j++)
| ~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
37 ms |
592 KB |
Output is correct |
| 4 |
Correct |
35 ms |
848 KB |
Output is correct |
| 5 |
Correct |
5 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1062 ms |
14920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
592 KB |
Output is correct |
| 2 |
Correct |
2 ms |
576 KB |
Output is correct |
| 3 |
Correct |
340 ms |
11644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
592 KB |
Output is correct |
| 5 |
Correct |
404 ms |
14236 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
508 KB |
Output is correct |
| 8 |
Correct |
162 ms |
15024 KB |
Output is correct |
| 9 |
Correct |
163 ms |
15040 KB |
Output is correct |
| 10 |
Correct |
267 ms |
14408 KB |
Output is correct |
| 11 |
Correct |
275 ms |
14920 KB |
Output is correct |
| 12 |
Correct |
231 ms |
14664 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
592 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
37 ms |
592 KB |
Output is correct |
| 4 |
Correct |
35 ms |
848 KB |
Output is correct |
| 5 |
Correct |
5 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
592 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
