// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 209, M = 50004;
int n, m, U[M], V[M], C[M], DR[M], P[N];
bool MR[N], Mark[M];
long long F[N], D[N][N];
vector < int > Adj[N];
inline long long SSSP(int st, int fn, int j)
{
memset(F, 63, sizeof(F));
memset(MR, 0, sizeof(MR));
F[st] = 0;
for (int __ = 1; __ <= n; __ ++)
{
int v = -1;
for (int i = 1; i <= n; i ++)
if (!MR[i] && (v == -1 || F[v] > F[i]))
v = i;
MR[v] = 1;
for (int i : Adj[v])
if (i != j && F[V[i]] > F[v] + C[i])
F[V[i]] = F[v] + C[i];
if (v == V[j])
if (F[U[j]] > F[v] + C[j])
F[U[j]] = F[v] + C[j];
}
return (F[fn]);
}
inline long long Solve(int st, int fn)
{
memset(P, 0, sizeof(P));
memset(F, 63, sizeof(F));
memset(MR, 0, sizeof(MR));
memset(Mark, 0, sizeof(Mark));
F[st] = 0;
for (int __ = 1; __ <= n; __ ++)
{
int v = -1;
for (int i = 1; i <= n; i ++)
if (!MR[i] && (v == -1 || F[v] > F[i]))
v = i;
MR[v] = 1;
for (int i : Adj[v])
if (F[V[i]] > F[v] + C[i])
F[V[i]] = F[v] + C[i],
P[V[i]] = i;
}
long long Mn = LLONG_MAX;
if (!P[fn])
return (Mn);
int v = fn;
while (v != st)
Mark[P[v]] = 1, v = U[P[v]];
for (int i = 1; i <= m; i ++)
if (!Mark[i])
Mn = min(Mn, D[fn][V[i]] + C[i] + D[U[i]][st] + DR[i] + F[fn]);
for (int j = 1; j <= m; j ++)
if (Mark[j])
Mn = min(Mn, SSSP(st, fn, j) + SSSP(fn, st, j) + DR[j]);
return (Mn);
}
int main()
{
scanf("%d%d", &n, &m);
memset(D, 63, sizeof(D));
for (int i = 1; i <= m; i ++)
{
scanf("%d%d%d%d", &U[i], &V[i], &C[i], &DR[i]);
D[U[i]][V[i]] = min(D[U[i]][V[i]], 1LL * C[i]);
Adj[U[i]].push_back(i);
}
for (int i = 1; i <= n; i ++)
D[i][i] = 0;
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]);
long long Mn = D[1][n] + D[n][1];
/*for (int i = 1; i <= m; i ++)
Mn = min(Mn, D[1][V[i]] + C[i] + D[U[i]][n] + D[n][V[i]] + C[i] + D[U[i]][1] + DR[i]);*/
Mn = min(Mn, Solve(1, n));
Mn = min(Mn, Solve(n, 1));
if (Mn > (long long)(1e10) * n)
Mn = -1;
return !printf("%lld\n", Mn);
}
Compilation message
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &U[i], &V[i], &C[i], &DR[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
760 KB |
Output is correct |
2 |
Correct |
14 ms |
764 KB |
Output is correct |
3 |
Correct |
18 ms |
760 KB |
Output is correct |
4 |
Correct |
21 ms |
760 KB |
Output is correct |
5 |
Correct |
6 ms |
760 KB |
Output is correct |
6 |
Correct |
15 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
760 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
760 KB |
Output is correct |
10 |
Correct |
118 ms |
800 KB |
Output is correct |
11 |
Correct |
124 ms |
888 KB |
Output is correct |
12 |
Correct |
119 ms |
760 KB |
Output is correct |
13 |
Incorrect |
16 ms |
760 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
1784 KB |
Output is correct |
2 |
Correct |
45 ms |
1784 KB |
Output is correct |
3 |
Correct |
47 ms |
1784 KB |
Output is correct |
4 |
Correct |
18 ms |
760 KB |
Output is correct |
5 |
Correct |
19 ms |
760 KB |
Output is correct |
6 |
Correct |
15 ms |
760 KB |
Output is correct |
7 |
Correct |
14 ms |
760 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Incorrect |
42 ms |
1784 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
760 KB |
Output is correct |
2 |
Correct |
15 ms |
760 KB |
Output is correct |
3 |
Correct |
37 ms |
1528 KB |
Output is correct |
4 |
Correct |
15 ms |
760 KB |
Output is correct |
5 |
Correct |
42 ms |
1784 KB |
Output is correct |
6 |
Correct |
5 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
760 KB |
Output is correct |
8 |
Incorrect |
39 ms |
1784 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
760 KB |
Output is correct |
2 |
Correct |
14 ms |
764 KB |
Output is correct |
3 |
Correct |
18 ms |
760 KB |
Output is correct |
4 |
Correct |
21 ms |
760 KB |
Output is correct |
5 |
Correct |
6 ms |
760 KB |
Output is correct |
6 |
Correct |
15 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
760 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
760 KB |
Output is correct |
10 |
Correct |
118 ms |
800 KB |
Output is correct |
11 |
Correct |
124 ms |
888 KB |
Output is correct |
12 |
Correct |
119 ms |
760 KB |
Output is correct |
13 |
Incorrect |
16 ms |
760 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |