//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9000000000000000000, INF32 = 2000000000, MOD = 1000000007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
void solve() {
ll n, m;
cin >> n >> m;
vector<ll> nc(m, 0);
vector<vector<tuple<ll, ll, ll>>> go(n);
bool f = true;
for (ll i = 0; i < m; i++) {
ll a, b, c, p;
cin >> a >> b >> c >> p;
a--;
b--;
c--;
if (p != 1) {
f = false;
}
go[a].emplace_back(b, c, p);
go[b].emplace_back(a, c, p);
}
if (true) {
vector<map<ll, vector<pair<ll, ll>>>> g(n);
vector<map<ll, ll>> sum(n);
for (ll i = 0; i < n; i++) {
for (auto[b, c, p] : go[i]) {
g[i][c].push_back(make_pair(p, b));
sum[i][c] += p;
}
}
for (ll i = 0; i < n; i++) {
for (auto&[c, _] : g[i]) {
sort(g[i][c].begin(), g[i][c].end());
reverse(g[i][c].begin(), g[i][c].end());
}
}
vector<ll> dist(n, INF64);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push(make_pair(0, 0));
dist[0] = 0;
while (!pq.empty()) {
auto[d, x] = pq.top();
pq.pop();
if (d != dist[x]) {
continue;
}
for (auto&[c, go] : g[x]) {
if (go.size() == 1) {
if (assign_min(dist[go[0].second], d)) {
pq.push(make_pair(d, go[0].second));
}
continue;
}
for (auto[p, i] : go) {
if (assign_min(dist[i], d + min(p, sum[x][c] - p))) {
pq.push(make_pair(dist[i], i));
}
if (g[i][c].size() > 1) {
ll j = g[i][c][0].second;
ll np = g[i][c][0].first;
if (assign_min(dist[j], d + sum[i][c] - np)) {
pq.push(make_pair(dist[j], j));
}
j = g[i][c][1].second;
np = g[i][c][1].first;
if (assign_min(dist[j], d + sum[i][c] - np)) {
pq.push(make_pair(dist[j], j));
}
}
}
}
}
cout << (dist.back() == INF64 ? -1 : dist.back()) << '\n';
return;
}
vector<vector<ll>> dist(n, vector<ll>(n, INF64));
priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> pq;
pq.push(make_tuple(0, 0, 0));
dist[0][0] = 0;
while (!pq.empty()) {
auto[d, x, pp] = pq.top();
pq.pop();
if (d != dist[x][pp]) {
continue;
}
for (auto[b, c, p] : go[x]) {
if (b != pp) {
nc[c] += p;
}
}
for (auto[b, c, p] : go[x]) {
if (b == pp) {
continue;
}
nc[c] -= p;
if (assign_min(dist[b][b], d + nc[c])) {
pq.push(make_tuple(dist[b][b], b, b));
}
if (assign_min(dist[b][x], d + p)) {
pq.push(make_tuple(dist[b][x], b, x));
}
nc[c] += p;
}
for (auto[b, c, p] : go[x]) {
if (b != pp) {
nc[c] -= p;
}
}
}
ll ans = INF64;
for (auto i : dist.back()) {
assign_min(ans, i);
}
cout << (ans == INF64 ? -1 : ans) << '\n';
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:55:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
55 | bool f = true;
| ^
Main.cpp: In function 'int main()':
Main.cpp:165:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | freopen("", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:166:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | freopen("", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
544 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
980 KB |
Output is correct |
10 |
Correct |
2 ms |
984 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
860 KB |
Output is correct |
15 |
Correct |
1 ms |
736 KB |
Output is correct |
16 |
Correct |
2 ms |
852 KB |
Output is correct |
17 |
Correct |
1 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
2 ms |
724 KB |
Output is correct |
20 |
Correct |
2 ms |
732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
24924 KB |
Output is correct |
2 |
Correct |
32 ms |
12752 KB |
Output is correct |
3 |
Correct |
110 ms |
26776 KB |
Output is correct |
4 |
Correct |
68 ms |
17684 KB |
Output is correct |
5 |
Correct |
538 ms |
77172 KB |
Output is correct |
6 |
Correct |
401 ms |
68964 KB |
Output is correct |
7 |
Correct |
143 ms |
55176 KB |
Output is correct |
8 |
Correct |
187 ms |
55624 KB |
Output is correct |
9 |
Correct |
210 ms |
55796 KB |
Output is correct |
10 |
Correct |
155 ms |
42704 KB |
Output is correct |
11 |
Correct |
66 ms |
35004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
544 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
980 KB |
Output is correct |
10 |
Correct |
2 ms |
984 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
860 KB |
Output is correct |
15 |
Correct |
1 ms |
736 KB |
Output is correct |
16 |
Correct |
2 ms |
852 KB |
Output is correct |
17 |
Correct |
1 ms |
852 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
2 ms |
724 KB |
Output is correct |
20 |
Correct |
2 ms |
732 KB |
Output is correct |
21 |
Correct |
99 ms |
24924 KB |
Output is correct |
22 |
Correct |
32 ms |
12752 KB |
Output is correct |
23 |
Correct |
110 ms |
26776 KB |
Output is correct |
24 |
Correct |
68 ms |
17684 KB |
Output is correct |
25 |
Correct |
538 ms |
77172 KB |
Output is correct |
26 |
Correct |
401 ms |
68964 KB |
Output is correct |
27 |
Correct |
143 ms |
55176 KB |
Output is correct |
28 |
Correct |
187 ms |
55624 KB |
Output is correct |
29 |
Correct |
210 ms |
55796 KB |
Output is correct |
30 |
Correct |
155 ms |
42704 KB |
Output is correct |
31 |
Correct |
66 ms |
35004 KB |
Output is correct |
32 |
Correct |
118 ms |
22656 KB |
Output is correct |
33 |
Correct |
91 ms |
23672 KB |
Output is correct |
34 |
Correct |
215 ms |
44624 KB |
Output is correct |
35 |
Correct |
148 ms |
35140 KB |
Output is correct |
36 |
Correct |
189 ms |
45372 KB |
Output is correct |
37 |
Correct |
177 ms |
51064 KB |
Output is correct |
38 |
Correct |
143 ms |
54856 KB |
Output is correct |
39 |
Correct |
100 ms |
30092 KB |
Output is correct |
40 |
Correct |
288 ms |
56976 KB |
Output is correct |
41 |
Correct |
275 ms |
57232 KB |
Output is correct |
42 |
Correct |
273 ms |
63152 KB |
Output is correct |
43 |
Correct |
115 ms |
29452 KB |
Output is correct |
44 |
Correct |
200 ms |
40776 KB |
Output is correct |
45 |
Correct |
187 ms |
49400 KB |
Output is correct |
46 |
Correct |
139 ms |
48084 KB |
Output is correct |
47 |
Correct |
169 ms |
49760 KB |
Output is correct |
48 |
Correct |
546 ms |
79896 KB |
Output is correct |