#include <bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define int long long
#define all(x) x.begin(), x.end()
typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef pair<int, int> pii; typedef map<int, int> mii; typedef map<int, vector<int>> mivi;
const int mod = 1000000007; // 10^9 + 7
const int INF = 1e17;
#define MAXN 200
#define MAXM 50000
struct Edge {
int u, v, c, d;
};
int n, m;
Edge edges[MAXM];
multiset<pii> adj[MAXN];
int dist[MAXN][MAXN];
int cost(){
priority_queue<pii> pq;
pq.push({0, 0});
vi dis(n, INF);
dis[0] = 0;
while (!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if (dis[u] != d) continue;
for (auto [v, cd] : adj[u]){
if (d + cd < dis[v]){
dis[v] = d + cd;
pq.push({dis[v], v});
}
}
}
int ret = dis[n-1];
fill(dis.begin(), dis.end(), INF);
dis[n-1] = 0;
pq.push({0, n-1});
while (!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if (dis[u] != d) continue;
for (auto [v, cd] : adj[u]){
if (d + cd < dis[v]){
dis[v] = d + cd;
pq.push({dis[v], v});
}
}
}
return ret + dis[0];
}
void REM(int u, int v, int c){ adj[u].erase(adj[u].find({v, c})); }
void ADD(int u, int v, int c){ adj[u].insert({v, c}); }
void solve(){
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)
dist[i][j] = INF;
dist[i][i] = 0;
adj[i].clear();
}
for (int i = 0; i < m; i++){
Edge &e = edges[i];
cin >> e.u >> e.v >> e.c >> e.d;
e.u--, e.v--;
ADD(e.u, e.v, e.c);
dist[e.u][e.v] = min(dist[e.u][e.v], e.c);
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
int ans = cost();
for (int i = 0; i < m; i++){
auto [u, v, c, d] = edges[i];
int p = min(dist[0][n-1], dist[0][v] + c + dist[u][n-1])
+ min(dist[n-1][0], dist[n-1][v] + c + dist[u][0])
+ d;
if (p < ans){
REM(u, v, c);
ADD(v, u, c);
ans = min(ans, cost() + d);
REM(v, u, c);
ADD(u, v, c);
}
}
cout << (ans >= INF ? -1 : ans) << endl;
}
int32_t main(){
#ifndef ONLINE_JUDGE
auto begin = chrono::high_resolution_clock::now();
freopen("sol.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;// cin >> T;
for (int i = 1; i <= T; i++){
#ifndef ONLINE_JUDGE
if (T != 1)
cout << "Test Case #" << i << endl;
#endif
solve();
}
#ifndef ONLINE_JUDGE
auto elapsed = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now() - begin);
cout << "Time Taken : " << (elapsed.count() * 1e-9) << " seconds" << endl;
#endif
return 0;
}
Compilation message
ho_t4.cpp: In function 'long long int cost()':
ho_t4.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | auto [d, u] = pq.top();
| ^
ho_t4.cpp:32:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | for (auto [v, cd] : adj[u]){
| ^
ho_t4.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
44 | auto [d, u] = pq.top();
| ^
ho_t4.cpp:47:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
47 | for (auto [v, cd] : adj[u]){
| ^
ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | auto [u, v, c, d] = edges[i];
| ^
ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen("sol.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
