| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1303091 | monaxia | Olympic Bus (JOI20_ho_t4) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
#define ordered_set tree<pair <ll, ll>, null_type, less<pair <ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ull Mod = 1e9 + 7;
constexpr ull sqr = 708;
constexpr ld EPS = 1e-12L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random_ll(ll l, ll r) {if (l > r) return -1; return uniform_int_distribution<ll>(l, r)(rng);}
struct edge{
ll u, v, w, d;
};
vector <edge> e;
ll dist[202][202];
int graph[202][202], se[202][202];
int n, m;
ll ans = 1e18;
void floyd(){
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++) dist[i][j] = graph[i][j];
for(int k = 1; k <= n; k ++){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
if(dist[i][k] <= 1e9 && dist[k][j] <= 1e9) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
vector <edge> ee;
void findpath(int u, int v){
if(dist[u][v] > 1e18) return;
for(int i = u; i != v;){
for(auto& [x, y, w, d] : e){
if(i != x) continue;
if(w + dist[u][x] + dist[y][v] == dist[u][v]){
ee.pb({x, y, w, d});
i = y;
break;
}
}
}
}
void solve(){
memset(dist, 0x3f3f3f3f, sizeof(dist));
memset(graph, 0x3f3f3f3f, sizeof(graph));
memset(se, 0x3f3f3f3f, sizeof(se));
cin >> n >> m;
for(int i = 1; i <= m; i ++){
ll u, v, w, d;
cin >> u >> v >> w >> d;
e.pb({u, v, w, d});
dist[u][v] = min(dist[u][v], w);
graph[u][v] = min(graph[u][v], w);
if(graph[u][v] != w) min(se[u][v], w);
}
for(int i = 1; i <= n; i ++) dist[i][i] = graph[i][i] = se[i][i] = 0;
floyd();
findpath(1, n);
findpath(n, 1);
for(auto& [u, v, w, d] : e){
if(dist[1][u] + w + dist[v][n] == dist[1][n] || dist[n][u] + w + dist[v][1] == dist[n][1]){
continue;
}
if(dist[1][v] + w + d + dist[u][n] < dist[1][n] || dist[n][v] + w + d + dist[u][1] < dist[n][1]) ee.pb({u, v, w, d});
}
ans = dist[1][n] + dist[n][1];
for(auto& [u, v, w, d] : ee){
ll prevu = graph[u][v], prevv = graph[v][u];
graph[v][u] = w + d;
if(graph[u][v] == w){
graph[u][v] = se[u][v];
}
floyd();
ans = min(ans, dist[1][n] + dist[n][1]);
graph[u][v] = prevu;
graph[v][u] = prevv;
}
if(ans > 1e17) ans = -1;
cout << ans;
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen("ZIP.inp", "r")){
freopen("ZIP.inp", "r", stdin);
freopen("ZIP.out", "w", stdout);
}
// return 0;
int t = 1;
// cin >> t;
while(t --){
solve();
cout << "\n";
}
cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}
// Whose eyes are those eyes?