#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii; typedef vector<int> vi;
struct Edge {
int u, v, c, d;
};
int n, m;
vector<multiset<pii>> adj;
int min_dist(int src, int dest){
vi dist(n, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [v, w] : adj[u]){
if (dist[v] == -1 || (d + w) < dist[v]){
dist[v] = d + w;
if (v != dest)
pq.push({dist[v], v});
}
}
}
return dist[dest];
}
int32_t main(){
cin >> n >> m;
adj.assign(n, multiset<pii>());
vector<Edge> edges(m);
for (auto &[u, v, c, d] : edges){
cin >> u >> v >> c >> d;
u--, v--;
adj[u].insert({v, c});
}
int ans = -1;
int fw = min_dist(0, n-1);
if (fw != -1){
int bw = min_dist(n-1, 0);
if (bw != -1)
ans = fw + bw;
}
for (auto [u, v, c, d] : edges){
adj[u].erase(adj[u].find({v, c}));
adj[v].insert({u, c});
int fw = min_dist(0, n-1), bw;
if (fw == -1)
goto rollback;
bw = min_dist(n-1, 0);
if (bw == -1)
goto rollback;
if (ans == -1 || (fw + d + bw) < ans)
ans = fw + d + bw;
rollback:
adj[v].erase(adj[v].find({u, c}));
adj[u].insert({v, c});
}
cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
42 ms |
348 KB |
Output is correct |
4 |
Correct |
47 ms |
348 KB |
Output is correct |
5 |
Correct |
16 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
7 ms |
348 KB |
Output is correct |
10 |
Correct |
67 ms |
348 KB |
Output is correct |
11 |
Correct |
65 ms |
520 KB |
Output is correct |
12 |
Correct |
75 ms |
520 KB |
Output is correct |
13 |
Correct |
17 ms |
540 KB |
Output is correct |
14 |
Correct |
25 ms |
536 KB |
Output is correct |
15 |
Correct |
7 ms |
348 KB |
Output is correct |
16 |
Correct |
26 ms |
540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1028 ms |
4948 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
548 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Execution timed out |
1097 ms |
4052 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
42 ms |
348 KB |
Output is correct |
4 |
Correct |
47 ms |
348 KB |
Output is correct |
5 |
Correct |
16 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
7 ms |
348 KB |
Output is correct |
10 |
Correct |
67 ms |
348 KB |
Output is correct |
11 |
Correct |
65 ms |
520 KB |
Output is correct |
12 |
Correct |
75 ms |
520 KB |
Output is correct |
13 |
Correct |
17 ms |
540 KB |
Output is correct |
14 |
Correct |
25 ms |
536 KB |
Output is correct |
15 |
Correct |
7 ms |
348 KB |
Output is correct |
16 |
Correct |
26 ms |
540 KB |
Output is correct |
17 |
Execution timed out |
1028 ms |
4948 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |