#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const ll linf = 1e18 + 1;
const int NMAX = 201;
vector <pll> vec[NMAX][NMAX];
map<pair<pii, pll>, bool> used;
bool comp1(pll a, pll b){
return a.f < b.f;
}
bool comp2(pll a, pll b){
return a.f + a.s < b.f + b.s;
}
bool comp3(pll a, pll b){
return 2 * a.f + a.s < 2 * b.f + b.s;
}
vector <pair<ll, pll> > g[NMAX][2];
ll d[NMAX][NMAX][4];
void dijk(int a, int b, int ind, int bb){
d[a][b][ind] = 0;
if(a == b) return;
set <pll> q;
q.insert({d[a][b][ind], a});
while(!q.empty()){
int v = q.begin()->s;
q.erase(q.begin());
for(auto x : g[v][bb]){
int to = x.f;
if(to == b) continue;
ll len = x.s.f;
if(d[to][b][ind] > d[v][b][ind] + len){
q.erase({d[to][b][ind], to});
d[to][b][ind] = d[v][b][ind] + len;
q.insert({d[to][b][ind], to});
}
}
}
}
int n;
ll get(int v, int ind){
ll x = d[n][v][0];
ll y = d[1][v][1];
ll mn1, mn2;
mn1 = d[v][v][3];
mn2 = d[v][v][0];
for(int i = 0; i < g[v][0].size(); i++){
if(i == ind) continue;
int xx = g[v][0][i].f;
ll len = g[v][0][i].s.f;
mn1 = min(mn1, d[xx][v][3] + len);
}
for(int i = 0; i < g[v][1].size(); i++){
int xx = g[v][1][i].f;
ll len = g[v][1][i].s.f;
mn2 = min(mn2, d[xx][v][0] + len);
}
if(ind != g[v][0].size()){
int xx = g[v][0][ind].f;
ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
mn2 = min(mn2, d[xx][v][0] + len);
}
x = min(x, mn1 + mn2);
mn1 = d[v][v][2];
mn2 = d[v][v][1];
for(int i = 0; i < g[v][0].size(); i++){
if(i == ind) continue;
int xx = g[v][0][i].f;
ll len = g[v][0][i].s.f;
mn1 = min(mn1, d[xx][v][2] + len);
}
for(int i = 0; i < g[v][1].size(); i++){
int xx = g[v][1][i].f;
ll len = g[v][1][i].s.f;
mn2 = min(mn2, d[xx][v][1] + len);
}
if(ind != g[v][0].size()){
int xx = g[v][0][ind].f;
ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
mn2 = min(mn2, d[xx][v][1] + len);
}
y = min(mn1 + mn2, y);
return x + y;
}
int main(){
//ios_base::sync_with_stdio(false); cin.tie(0);
int m; cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v;
ll c, d; cin >> u >> v >> c >> d;
vec[u][v].pb({c, d});
}
//cout << 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(vec[i][j].empty()) continue;
sort(vec[i][j].begin(), vec[i][j].end(), comp1);
g[i][0].pb({j, vec[i][j][0]});
used[{{i, j}, vec[i][j][0]}] = true;
sort(vec[i][j].begin(), vec[i][j].end(), comp2);
if(!used[{{i, j},vec[i][j][0]}])
g[i][0].pb({j, vec[i][j][0]}), used[{{i, j}, vec[i][j][0]}] = true;;
sort(vec[i][j].begin(), vec[i][j].end(), comp3);
if(!used[{{i, j},vec[i][j][0]}])
g[i][0].pb({j, vec[i][j][0]}), used[{{i, j}, vec[i][j][0]}] = true;;
}
}
// cout << 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 0; k < 4; k++){
d[i][j][k] = linf;
}
}
}
for(int i = 1; i <= n; i++){
for(auto to : g[i][0]){
int x = to.f;
pll v = to.s;
g[x][1].pb({i, v});
}
}
//cout << 1;
for(int i = 1; i <= n; i++){
dijk(1, i, 0, 0);
dijk(n, i, 1, 0);
dijk(1, i, 2, 1);
dijk(n, i, 3, 1);
}
//cout << 1;
ll ans = linf;
for(int i = n; i >= 1; i--){
for(int j = 0; j < g[i][0].size(); j++){
//cout << i << ' ' << g[i][0][j].f << ' ' << get(i, j) << "\n";
ans = min(ans, get(i, j));
}
}
if(ans == linf) cout << -1 << "\n";
else cout << ans;
return 0;
}
Compilation message
ho_t4.cpp: In function 'long long int get(int, int)':
ho_t4.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < g[v][0].size(); i++){
| ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < g[v][1].size(); i++){
| ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:72:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(ind != g[v][0].size()){
| ~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0; i < g[v][0].size(); i++){
| ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < g[v][1].size(); i++){
| ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:91:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(ind != g[v][0].size()){
| ~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int j = 0; j < g[i][0].size(); j++){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2516 KB |
Output is correct |
| 3 |
Correct |
44 ms |
2704 KB |
Output is correct |
| 4 |
Correct |
45 ms |
2728 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2516 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1276 KB |
Output is correct |
| 10 |
Correct |
54 ms |
2684 KB |
Output is correct |
| 11 |
Correct |
54 ms |
2712 KB |
Output is correct |
| 12 |
Correct |
53 ms |
2708 KB |
Output is correct |
| 13 |
Incorrect |
16 ms |
2644 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
356 ms |
9316 KB |
Output is correct |
| 2 |
Correct |
320 ms |
9144 KB |
Output is correct |
| 3 |
Correct |
329 ms |
9592 KB |
Output is correct |
| 4 |
Correct |
47 ms |
2812 KB |
Output is correct |
| 5 |
Correct |
30 ms |
2668 KB |
Output is correct |
| 6 |
Correct |
7 ms |
2616 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2476 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
1236 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2516 KB |
Output is correct |
| 3 |
Correct |
197 ms |
9348 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2580 KB |
Output is correct |
| 5 |
Correct |
234 ms |
10240 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 8 |
Incorrect |
178 ms |
9196 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2516 KB |
Output is correct |
| 3 |
Correct |
44 ms |
2704 KB |
Output is correct |
| 4 |
Correct |
45 ms |
2728 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2516 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1276 KB |
Output is correct |
| 10 |
Correct |
54 ms |
2684 KB |
Output is correct |
| 11 |
Correct |
54 ms |
2712 KB |
Output is correct |
| 12 |
Correct |
53 ms |
2708 KB |
Output is correct |
| 13 |
Incorrect |
16 ms |
2644 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
