#include<bits/stdc++.h>
using namespace std;
const int N = 201, M = 5e4+1;
const int INF = 1e9+1;
int n, m, u[M], v[M];
long long c[M], d[M];
long long G[N][N], W[N][N];
pair<long long, int> shortest[N][2];
long long solve(int p, int q) {
long long ans = INF;
for(int i=0; i<m; ++i) {
long long path[2] = {0, 0};
path[1] = G[q][v[i]] + c[i] + d[i] + G[u[i]][p];
path[0] = INF;
if(G[p][u[i]] + W[u[i]][v[i]] + G[v[i]][q] > G[p][q]) path[0] = G[p][q];
else for(int j=1; j<=n; ++j) {
if(G[p][j] > G[p][u[i]]) continue;
for(int k=1; k<=n; ++k) { if(k==j) continue;
if(G[k][q] >= G[u[i]][q] || (j==u[i] && k==v[i])) continue;
path[0] = min(path[0], G[p][j] + W[j][k] + G[k][q]);
}
}
ans = min(ans, path[0] + path[1]);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
G[i][j] = INF;
W[i][j] = INF;
}
G[i][i] = 0;
}
for(int i=0; i<m; ++i) {
cin>>u[i]>>v[i]>>c[i]>>d[i];
G[u[i]][v[i]] = min(G[u[i]][v[i]], c[i]);
W[u[i]][v[i]] = min(W[u[i]][v[i]], c[i]);
}
for(int k=1; k<=n; ++k) {
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
}
}
for(int i=1; i<=n; ++i) {
shortest[i][0] = shortest[i][1] = make_pair(INF, 0);
for(int j=1; j<=n; ++j) {
if(i==j) continue;
int path = G[1][i] + W[i][j] + G[j][n];
if(path <= shortest[i][0].first) {
shortest[i][1] = shortest[i][0];
shortest[i][0] = {path, j};
}
else if(path < shortest[i][1].first) {
shortest[i][1] = {path, j};
}
}
}
long long ans = min({G[1][n]+G[n][1], solve(1, n), solve(n, 1)});
if(ans >= INF) cout<<-1;
else cout<<ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
118 ms |
1024 KB |
Output is correct |
2 |
Correct |
19 ms |
1024 KB |
Output is correct |
3 |
Correct |
15 ms |
1024 KB |
Output is correct |
4 |
Correct |
14 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
13 ms |
1024 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
3192 KB |
Output is correct |
2 |
Correct |
34 ms |
3064 KB |
Output is correct |
3 |
Correct |
39 ms |
3320 KB |
Output is correct |
4 |
Incorrect |
14 ms |
1024 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
1024 KB |
Output is correct |
2 |
Correct |
23 ms |
1024 KB |
Output is correct |
3 |
Execution timed out |
1087 ms |
2560 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
118 ms |
1024 KB |
Output is correct |
2 |
Correct |
19 ms |
1024 KB |
Output is correct |
3 |
Correct |
15 ms |
1024 KB |
Output is correct |
4 |
Correct |
14 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
13 ms |
1024 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |