#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const llong inf = 1e18;
int n, m;
int U[50001], V[50001], C[50001];
bool used[201];
void dijkstra(vector<int> edge[], llong D[], int P[], int s) {
for (int i = 1; i <= n; ++i) D[i] = inf, used[i] = 0;
D[s] = 0;
while (1) {
int x = 0;
llong d = inf;
for (int i = 1; i <= n; ++i) {
if (!used[i] && D[i] < d) x = i, d = D[i];
}
if (!x) break;
used[x] = 1;
for (int it : edge[x]) {
llong nd = d + C[it];
int i = U[it] ^ V[it] ^ x;
if (nd < D[i]) {
D[i] = nd;
P[i] = it;
}
}
}
}
llong ans[50001];
llong dist1[201], dist2[201], dist3[201];
int prev1[201], prev2[201], prev3[201];
vector<int> pedge[201], redge[201], edge[201];
void solve(int a, int b) {
dijkstra(pedge, dist1, prev1, a);
ans[0] += dist1[b];
dijkstra(redge, dist2, prev2, b);
for (int i = 1; i <= m; ++i) {
if (dist1[V[i]] >= inf || dist2[U[i]] >= inf) {
ans[i] += inf;
continue;
}
bool r = 0;
if (!r) for (int j = V[i]; j != a; j = U[prev1[j]]) if (i == prev1[j]) { r = 1; break; }
if (!r) for (int j = U[i]; j != b; j = V[prev2[j]]) if (i == prev2[j]) { r = 1; break; }
if (!r) {
ans[i] += dist1[V[i]] + C[i] + dist2[U[i]];
continue;
}
for (int j = 1; j <= n; ++j) edge[j].clear();
for (int j = 1; j <= m; ++j) {
edge[i != j ? U[j] : V[j]].push_back(j);
}
dijkstra(edge, dist3, prev3, a);
ans[i] += dist3[b];
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> U[i] >> V[i] >> C[i] >> ans[i];
pedge[U[i]].push_back(i);
redge[V[i]].push_back(i);
}
solve(1, n); solve(n, 1);
llong ret = inf;
for (int i = 0; i <= m; ++i) ret = min(ret, ans[i]);
printf("%lld\n", ret < inf ? ret : -1);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
75 ms |
384 KB |
Output is correct |
4 |
Correct |
77 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
471 ms |
3356 KB |
Output is correct |
2 |
Incorrect |
462 ms |
3192 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
384 KB |
Output is correct |
2 |
Correct |
9 ms |
384 KB |
Output is correct |
3 |
Correct |
393 ms |
2560 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
496 ms |
3448 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
23 ms |
2808 KB |
Output is correct |
9 |
Correct |
22 ms |
2816 KB |
Output is correct |
10 |
Correct |
254 ms |
3324 KB |
Output is correct |
11 |
Correct |
252 ms |
3192 KB |
Output is correct |
12 |
Correct |
252 ms |
3320 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
253 ms |
3192 KB |
Output is correct |
20 |
Correct |
249 ms |
3192 KB |
Output is correct |
21 |
Correct |
250 ms |
3320 KB |
Output is correct |
22 |
Correct |
259 ms |
3200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
75 ms |
384 KB |
Output is correct |
4 |
Correct |
77 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |