#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
const int MX_N = 205;
const int MX_M = 5e4+5;
const long long INF = 1e18;
struct Edge { int v, c, d, i; };
int N, M;
vector<Edge> al[MX_N];
long long dist[2][MX_N];
void dijkstra(int s, vector<Edge>* al, long long* dist, int blocked) {
fill(dist+1,dist+1+N,INF);
dist[s] = 0;
bool done[N+1];
fill(done+1,done+1+N,0);
while (true) {
int u = -1;
FOR(v,1,N) if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;
if (u == -1) break;
done[u] = 1;
for (auto e : al[u]) if (e.i != blocked) {
if (dist[u] + e.c < dist[e.v]) {
dist[e.v] = dist[u] + e.c;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
FOR(i,1,M){
int U, V, C, D; cin >> U >> V >> C >> D;
al[U].push_back({V,C,D,i});
}
dijkstra(1,al,dist[0],-1);
dijkstra(N,al,dist[1],-1);
long long ans = min(INF, (long long) dist[0][N] + dist[1][1]);
FOR(u,1,N){
for (auto& e : al[u]) {
al[e.v].push_back({u,e.c,e.d,M+1});
dijkstra(1,al,dist[0],e.i);
dijkstra(N,al,dist[1],e.i);
al[e.v].pop_back();
ans = min(ans, (long long) dist[0][N] + dist[1][1] + e.d);
}
}
cout << (ans == INF ? -1 : ans) << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
504 KB |
Output is correct |
2 |
Correct |
52 ms |
384 KB |
Output is correct |
3 |
Correct |
211 ms |
384 KB |
Output is correct |
4 |
Correct |
217 ms |
504 KB |
Output is correct |
5 |
Correct |
15 ms |
384 KB |
Output is correct |
6 |
Correct |
51 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
8 ms |
384 KB |
Output is correct |
10 |
Correct |
216 ms |
384 KB |
Output is correct |
11 |
Correct |
213 ms |
376 KB |
Output is correct |
12 |
Correct |
215 ms |
504 KB |
Output is correct |
13 |
Correct |
214 ms |
384 KB |
Output is correct |
14 |
Correct |
203 ms |
504 KB |
Output is correct |
15 |
Correct |
205 ms |
384 KB |
Output is correct |
16 |
Correct |
200 ms |
456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1083 ms |
1784 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
209 ms |
504 KB |
Output is correct |
2 |
Correct |
50 ms |
384 KB |
Output is correct |
3 |
Execution timed out |
1091 ms |
1920 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
504 KB |
Output is correct |
2 |
Correct |
52 ms |
384 KB |
Output is correct |
3 |
Correct |
211 ms |
384 KB |
Output is correct |
4 |
Correct |
217 ms |
504 KB |
Output is correct |
5 |
Correct |
15 ms |
384 KB |
Output is correct |
6 |
Correct |
51 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
8 ms |
384 KB |
Output is correct |
10 |
Correct |
216 ms |
384 KB |
Output is correct |
11 |
Correct |
213 ms |
376 KB |
Output is correct |
12 |
Correct |
215 ms |
504 KB |
Output is correct |
13 |
Correct |
214 ms |
384 KB |
Output is correct |
14 |
Correct |
203 ms |
504 KB |
Output is correct |
15 |
Correct |
205 ms |
384 KB |
Output is correct |
16 |
Correct |
200 ms |
456 KB |
Output is correct |
17 |
Execution timed out |
1083 ms |
1784 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |