#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define int long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 205, mxm = 50005;
struct E{
ll v, c, e, id;
};
ll d[mxn + 1];
vt<E>adj[mxn + 1], rev[mxn + 1];
E edge[mxm + 1];
bool used[mxm + 1];
pii trace[mxn + 1], trace2[mxn + 1];
int n, m;
ll dis[205][205];
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
forr(i, 1, n + 1){
forr(j, 1, n + 1){
dis[i][j] = 1e18;
}
}
forr(i, 0, m){
int u, v, c, e; cin >> u >> v >> c >> e;
adj[u].pb({v, c, e, i}); rev[v].pb({u, c, e, i});
edge[i] = {u, v, c, e};
}
dis[1][1] = 0;
priority_queue<pll, vt<pll>, greater<pll>>pq; pq.push({dis[1][1], 1});
while(!pq.empty()){
auto [dd, u] = pq.top(); pq.pop();
if(dis[1][u] != dd)continue;
for(auto [v, c, e, id]: adj[u]){
if(dis[1][v] > dis[1][u] + c){
dis[1][v] = dis[1][u] + c;
pq.push({dis[1][v], v});
trace[v] = make_pair(id, u);
}
}
}
dis[n][n] = 0;
pq.push({dis[n][n], n});
while(!pq.empty()){
auto [dd, u] = pq.top(); pq.pop();
for(auto [v, c, e, id]: rev[u]){
if(dis[v][n] > dis[u][n] + c){
dis[v][n] = dis[u][n] + c;
pq.push({dis[v][n], v});
}
}
}
pq.push({dis[n][n], n});
while(!pq.empty()){
auto [dd, u] = pq.top(); pq.pop();
for(auto [v, c, e, id]: adj[u]){
if(dis[n][v] > dis[n][u] + c){
dis[n][v] = dis[n][u] + c;
pq.push({dis[n][v], v});
trace2[v] = make_pair(id, u);
}
}
}
pq.push({dis[1][1], 1});
while(!pq.empty()){
auto [dd, u] = pq.top(); pq.pop();
for(auto [v, c, e, id]: rev[u]){
if(dis[v][1] > dis[u][1] + c){
dis[v][1] = dis[u][1] + c;
pq.push({dis[v][1], v});
}
}
}
if(dis[1][n] < 1e18){
int v = n;
while(v != 1){
used[trace[v].fi] = 1;
v = trace[v].se;
}
}
if(dis[n][1] < 1e18){
int v = 1;
while(v != n){
used[trace2[v].fi] = 1;
v = trace2[v].se;
}
}
ll ans = dis[1][n] + dis[n][1];
for(int i = 0; i < m; i++){
auto [u, v, c, e] = edge[i];
if(!used[i]){
ll ton = min(dis[1][n], dis[1][v] + dis[u][n] + c);
ll to1 = min(dis[n][1], dis[n][v] + dis[u][1] + c);
ans = min(ans, ton + to1 + e);
}else{
forr(i, 1, n + 1)d[i] = 1e18;
d[1] = 0; pq.push({d[1], 1});
while(!pq.empty()){
auto [dd, uu] = pq.top(); pq.pop();
if(d[uu] != dd)continue;
for(auto [vv, cc, ee, id]: adj[uu]){
if(id == i)continue;
if(d[vv] > d[uu] + cc){
d[vv] = d[uu] + cc; pq.push({d[vv], vv});
}
}
if(uu == u){
if(d[v] > d[uu] + c){
d[v] = d[uu] + c;
pq.push({d[v], v});
}
}
}
ll curr = d[n];
forr(i, 1, n + 1)d[i] = 1e18;
d[n] = 0; pq.push({d[n], n});
while(!pq.empty()){
auto [dd, uu] = pq.top(); pq.pop();
if(d[uu] != dd)continue;
for(auto [vv, cc, ee, id]: adj[uu]){
if(id == i)continue;
if(d[vv] > d[uu] + cc){
d[vv] = d[uu] + cc; pq.push({d[vv], vv});
}
}
if(uu == u){
if(d[v] > d[uu] + c){
d[v] = d[uu] + c;
pq.push({d[v], v});
}
}
}
curr += d[1];
ans = min(ans, curr);
}
}
cout << ans;
return(0);
}
Compilation message
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | auto [dd, u] = pq.top(); pq.pop();
| ^
ho_t4.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | for(auto [v, c, e, id]: adj[u]){
| ^
ho_t4.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | auto [dd, u] = pq.top(); pq.pop();
| ^
ho_t4.cpp:62:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
62 | for(auto [v, c, e, id]: rev[u]){
| ^
ho_t4.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | auto [dd, u] = pq.top(); pq.pop();
| ^
ho_t4.cpp:73:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
73 | for(auto [v, c, e, id]: adj[u]){
| ^
ho_t4.cpp:84:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | auto [dd, u] = pq.top(); pq.pop();
| ^
ho_t4.cpp:85:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for(auto [v, c, e, id]: rev[u]){
| ^
ho_t4.cpp:112:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
112 | auto [u, v, c, e] = edge[i];
| ^
ho_t4.cpp:123:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
123 | auto [dd, uu] = pq.top(); pq.pop();
| ^
ho_t4.cpp:125:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
125 | for(auto [vv, cc, ee, id]: adj[uu]){
| ^
ho_t4.cpp:142:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
142 | auto [dd, uu] = pq.top(); pq.pop();
| ^
ho_t4.cpp:144:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
144 | for(auto [vv, cc, ee, id]: adj[uu]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
23 ms |
7084 KB |
Output is correct |
| 3 |
Correct |
23 ms |
7124 KB |
Output is correct |
| 4 |
Correct |
2 ms |
852 KB |
Output is correct |
| 5 |
Correct |
2 ms |
724 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
