| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1266208 | nguyn | Olympic Bus (JOI20_ho_t4) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
const ll inf = 1e18;
struct Edge {
int u, v, c, d;
} edges[50005];
vector<int> g[205];
int n, m;
ll d[205][205];
ll d0[205];
int used[50005];
ll dijkstra(int s, int type) {
vector<int> vis(n + 3, 0);
vector<int> trace(n + 3, 0);
for (int i = 1; i <= n; i++) {
d0[i] = inf;
}
d0[s] = 0;
d0[0] = inf;
for (int i = 1; i <= n; i++) {
int u = 0;
for (int j = 1; j <= n; j++) {
if (!vis[j] && d0[u] > d0[j]) {
u = j;
}
}
vis[u] = 1;
if (d0[u] == inf || u == 0) break;
for (int id : g[u]) {
if (d0[u] + edges[id].c < d0[edges[id].v]) {
d0[edges[id].v] = d0[u] + edges[id].c;
trace[edges[id].v] = id;
}
}
}
int u;
if (s == 1) u = n;
if (s == n) u = 1;
if (d0[u] >= inf) return inf;
if (type == 1) {
while(u != s) {
used[trace[u]] = 1;
u = edges[trace[u]].u;
}
}
return d0[u];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
d[i][j] = inf;
}
}
for (int i = 1; i <= m; i++) {
int u, v, c, dd;
cin >> u >> v >> c >> dd;
g[u].pb(i);
edges[i] = {u, v, c, dd};
d[u][v] = min(d[u][v], c);
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
ll res = d[1][n] + d[n][1];
dijkstra(1, 1);
dijkstra(n, 1);
for (int i = 1; i <= m; i++) {
int u = edges[i].u;
int v = edges[i].v;
int c = edges[i].c;
int dd = edges[i].d;
ll tmp = min(d[1][n], d[1][v] + c + d[u][n]) + min(d[n][1], d[n][v] + c + d[u][1]) + dd;
if (!used[i]) {
res = min(res, tmp);
}
else {
g[u].erase(find(g[u].begin(), g[u].end(), i));
swap(edges[i].u, edges[i].v);
g[v].pb(i);
res = min(res, dijkstra(1, 0) + dijkstra(n, 0) + dd);
g[v].pop_back();
swap(edges[i].u, edges[i].v);
g[u].pb(i);
}
}
if (res >= inf) {
cout << -1;
}
else cout << res;
}