Submission #368201

#TimeUsernameProblemLanguageResultExecution timeMemory
368201vaavenOlympic Bus (JOI20_ho_t4)C++14
0 / 100
57 ms3692 KiB
#include <iostream> #include <vector> #include <algorithm> #include <math.h> #include <set> #include <stack> #include <iomanip> #include <bitset> #include <map> #include <cassert> #include <array> #include <queue> #include <cstring> #include <random> #include <unordered_set> #include <unordered_map> #define pqueue priority_queue #define pb(x) push_back(x) // #define endl '\n' #define all(x) x.begin(), x.end() #define int long long using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int> > vvi; // typedef tuple<ll, ll, ll> tiii; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef vector<bool> vb; typedef vector<string> vs; typedef vector<char> vc; const int inf = 1e9 + 228; const ll infll = 1e18; const ll mod = 1e9 + 7; const ll mod2 = 998244353; const ld eps = 1e-14; void fast_io(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("a.in", "r", stdin); // freopen("outputik.txt", "w", stdout); } struct edge{ int v, c, d; edge(){} edge(int v, int c, int d): v(v), c(c), d(d){} }; vector<edge> g[201]; int dist[201][201]; void solve(){ int n, m; cin >> n >> m; for(auto &i:dist) for(auto &j:i) j = infll; for(int i=0; i<m; i++){ int a, b, c, d; cin >> a >> b >> c >> d; a--, b--; g[b].pb(edge(a, c, d)); dist[a][b] = c; } for(int i=0; i<n; i++){ dist[i][i] = 0; } for(int k=0; k<n; k++){ for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } int ans = dist[0][n-1] + dist[n-1][0]; for(int i=0; i<n; i++){ multiset<int> kek; if(g[i].size() <= 1) continue; for(edge j:g[i]){ kek.insert(dist[0][j.v] + j.c); } for(edge j:g[i]){ kek.erase(kek.find(dist[0][j.v] + j.c)); ans = min(ans, *(kek.begin()) + j.d + dist[j.v][n-1] + dist[n-1][0]); // ans = min(ans, *(kek.begin()) + j.c + dist[j.v][n-1]); kek.insert(dist[0][j.v] + j.c); } } for(int i=0; i<n; i++){ multiset<int> kek; if(g[i].size() <= 1) continue; // cout << i << endl; for(edge j:g[i]){ kek.insert(dist[n-1][j.v] + j.c); } for(edge j:g[i]){ kek.erase(kek.find(dist[n-1][j.v] + j.c)); ans = min(ans, *(kek.begin()) + j.d + dist[0][n-1] + dist[i][0]); kek.insert(dist[n-1][j.v] + j.c); // ans = min(ans, *(kek.begin()) + j.c + dist[j.v][n-1]); } } if(ans >= infll){ cout << -1 << endl; return; } cout << ans << endl; } signed main(){ fast_io(); // ;(time(NULL)); cout << fixed << setprecision(10); int q = 1; // cin >> q; while(q--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...