#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 205, M = 5e4 + 7;
const int INF = 1e18 + 39;
struct Edge{
int v, u, c, d;
Edge() {}
Edge(int v, int u, int c, int d) : v(v), u(u), c(c), d(d) {}
};
int n ,m;
Edge edg[M];
void dijks(int st, int d[], int p[], bool rev, vector<int> g[], int ign) {
for (int i = 0; i < n; i++) {
d[i] = INF;
p[i] = -1;
}
d[st] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({d[st], st});
while (!q.empty()) {
auto cur = q.top();
q.pop();
int v = cur.second;
if (d[v] != cur.first)
continue;
for (auto id : g[v]) {
if (id == ign) continue;
int w = edg[id].c, u = rev ? edg[id].v : edg[id].u;
if (d[v] + w < d[u]) {
d[u] = d[v] + w;
p[u] = id;
q.push({d[u], u});
}
}
}
}
vector<int> g[N], gr[N];
int d1[N], dn[N];
int d1r[N], dnr[N];
int p1[N], pn[N];
int p1r[N], pnr[N];
bool bad1[N], badn[N];
bool bad1r[N], badnr[N];
int tmp_d[N], tmp_p[N];
int get_d1(int v, int ign) {
if (bad1[ign]) {
dijks(0, tmp_d, tmp_p, 0, g, ign);
return tmp_d[v];
}
return d1[v];
}
int get_dn(int v, int ign) {
if (badn[ign]) {
dijks(n - 1, tmp_d, tmp_p, 0, g, ign);
return tmp_d[v];
}
return dn[v];
}
int get_d1r(int v, int ign) {
if (bad1r[ign]) {
dijks(0, tmp_d, tmp_p, 1, gr, ign);
return tmp_d[v];
}
return d1r[v];
}
int get_dnr(int v, int ign) {
if (badnr[ign]) {
dijks(n - 1, tmp_d, tmp_p, 1, gr, ign);
return tmp_d[v];
}
return dnr[v];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> edg[i].v >> edg[i].u >> edg[i].c >> edg[i].d;
edg[i].v--;
edg[i].u--;
g[edg[i].v].push_back(i);
gr[edg[i].u].push_back(i);
}
dijks(0, d1, p1, 0, g, -1);
dijks(0, d1r, p1r, 1, gr, -1);
dijks(n - 1, dn, pn, 0, g, -1);
dijks(n - 1, dnr, pnr, 1, gr, -1);
for (int i = 0; i < n; i++) {
if (~p1[i])
bad1[p1[i]] = 1;
if (~pn[i])
badn[pn[i]] = 1;
if (~p1r[i])
bad1r[p1r[i]] = 1;
if (~pnr[i])
badnr[pnr[i]] = 1;
}
int ans = min(INF, d1[n - 1] + dn[0]);
for (int i = 0; i < m; ++i) {
int dist1 = min(get_d1(n - 1, i), get_d1(edg[i].u, i) + get_dnr(edg[i].v, i) + edg[i].c);
int distn = min(get_dn(0, i), get_dn(edg[i].u, i) + get_d1r(edg[i].v, i) + edg[i].c);
ans = min(ans, dist1 + distn + edg[i].d);
}
if (ans == INF)
cout << "-1\n";
else
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
26 ms |
7424 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |