#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #pragma GCC optimize("Ofast,unroll-loops,inline-functions,no-stack-protector,03") #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native") #pragma clang loop vectorize(enable) #pragma clang loop interleave(enable) #define int long long #define sz(x) (int)x.size() #define F first #define S second #define pb push_back #define nl '\n' #define o_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair<int, int> pii; void file( string s = "" ) { if( s.empty() ) return; freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } const int N = 2e5 + 2; const int N1 = 1e6 + 2; const int inf = 1e9; const int INF = 1e18; const int mod = 1e9 + 7; const double eps = 1e-9; int T = 1, n, m; vector< array<int, 3> > g[300]; int dist( int s, int t ) { vector< int > d(n + 1, INF); priority_queue< pii > q; d[s] = 0; q.push({0, s}); while( !q.empty() ) { auto [d1, v] = q.top(); q.pop(); if( -d1 > d[v] ) continue; for( auto [to, w, dd]: g[v] ) if( d[v] + w < d[to] ) { d[to] = d[v] + w; q.push({-d[to], to}); } } return d[t]; } vector< int > dijkstra( int s ) { vector< int > d(n + 1, INF); priority_queue< pii > q; d[s] = 0; q.push({0, s}); while( !q.empty() ) { auto [d1, v] = q.top(); q.pop(); if( -d1 > d[v] ) continue; for( auto [to, w, dd]: g[v] ) if( d[v] + w < d[to] ) { d[to] = d[v] + w; q.push({-d[to], to}); } } return d; } void solve() { cin >>n >>m; vector< array<int, 4> > e; for( int i = 1, u, v, c, d; i <= m; ++i ) { cin >>u >>v >>c >>d; g[u].pb({v, c, d}); e.pb({u, v, c, d}); } vector< vector< int > > ds(n + 1); for( int i = 1; i <= n; ++i ) ds[i] = dijkstra(i); int ans = ds[1][n] + ds[n][1]; for( auto [u, v, c, d]: e ) if( ans > min(ds[1][n], ds[1][v] + ds[u][n]) + min(ds[n][1], ds[n][v] + ds[u][1]) + c + d ) { array<int, 3> idc = {v, c, d}; g[u].erase(find(g[u].begin(), g[u].end(), idc)); g[v].pb({u, c, d}); ans = min(ans, dist(1, n) + dist(n, 1) + d); g[v].pop_back(); g[u].pb(idc); } cout <<(ans >= INF ? -1 : ans); } signed main() { file(""); ios_base::sync_with_stdio(false); cin.tie(nullptr); // cin >>T; while( T-- ) solve(); }

ho_t4.cpp: In function 'void file(std::string)':
ho_t4.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~