#include <bits/stdc++.h>
using namespace std;
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t);
#define forr(i, l, r) for(int i=l; i<r; i++)
#define frange(i, l) forr(i, 0, l)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef long long lli;
typedef vector<vi> vvi;
typedef vector<lli> vll;
typedef vector<bool> vb;
typedef set<int> seti;
void usaco() {
freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
}
struct Edge {
int a, b;
lli c, d;
};
int main() {
// usaco();
int n, m;
scd(n);
scd(m);
vector<seti> graph(n+1);
vector<Edge> edg(m);
vector<vll> dist(n+1, vll(n+1, 1e18));
forr(i, 1, n+1) dist[i][i] = 0;
frange(i, m) {
int a, b;
lli c, d;
scd(a);
scd(b);
sclld(c);
sclld(d);
graph[a].insert(i);
edg[i].a = a;
edg[i].b = b;
edg[i].c = c;
edg[i].d = d;
dist[a][b] = min(dist[a][b], c);
}
forr(k, 1, n+1) {
forr(i, 1, n+1) {
forr(j, 1, n+1) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
lli mi = dist[1][n]+dist[n][1];
frange(i, m) {
auto p = edg[i];
lli d1 = min(dist[1][n], dist[1][p.b] + dist[p.a][n] + p.c);
lli d2 = min(dist[n][1], dist[n][p.b] + dist[p.a][1] + p.c);
if(d1 + d2 + p.d < mi) {
graph[edg[i].a].erase(i);
graph[edg[i].b].insert(i);
swap(edg[i].a, edg[i].b);
priority_queue<pair<lli, int>> pq;
vll dist(n+1, 1e18);
dist[1] = 0;
pq.push(mp(0, 1));
vb vis(n+1);
while(pq.size()) {
auto p = pq.top();
pq.pop();
if(vis[p.s]) continue;
vis[p.s] = true;
for(auto x : graph[p.s]) {
auto e = edg[x];
if(dist[p.s] + e.c < dist[e.b]) {
dist[e.b] = dist[p.s] + e.c;
pq.push(mp(-dist[e.b], e.b));
}
}
}
lli dt1 = dist[n];
dist = vll(n+1, 1e18);
dist[n] = 0;
pq.push(mp(0, n));
vis = vb(n+1);
while(pq.size()) {
auto p = pq.top();
pq.pop();
if(vis[p.s]) continue;
vis[p.s] = true;
for(auto x : graph[p.s]) {
auto e = edg[x];
if(dist[p.s] + e.c < dist[e.b]) {
dist[e.b] = dist[p.s] + e.c;
pq.push(mp(-dist[e.b], e.b));
}
}
}
lli dt2 = dist[1];
mi = min(mi, dt1+dt2+p.d);
swap(edg[i].a, edg[i].b);
graph[edg[i].a].insert(i);
graph[edg[i].b].erase(i);
}
}
printf("%lld", mi);
}
Compilation message
ho_t4.cpp: In function 'void usaco()':
ho_t4.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
ho_t4.cpp:36:2: note: in expansion of macro 'scd'
36 | scd(n);
| ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
ho_t4.cpp:37:2: note: in expansion of macro 'scd'
37 | scd(m);
| ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
ho_t4.cpp:46:3: note: in expansion of macro 'scd'
46 | scd(a);
| ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
ho_t4.cpp:47:3: note: in expansion of macro 'scd'
47 | scd(b);
| ^~~
ho_t4.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
6 | #define sclld(t) scanf("%lld", &t);
| ~~~~~^~~~~~~~~~~~
ho_t4.cpp:48:3: note: in expansion of macro 'sclld'
48 | sclld(c);
| ^~~~~
ho_t4.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
6 | #define sclld(t) scanf("%lld", &t);
| ~~~~~^~~~~~~~~~~~
ho_t4.cpp:49:3: note: in expansion of macro 'sclld'
49 | sclld(d);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
856 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
5260 KB |
Output is correct |
| 2 |
Correct |
35 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
38 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
8 ms |
856 KB |
Output is correct |
| 5 |
Correct |
7 ms |
856 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
600 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
856 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
856 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
