#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int, vector<pair<int, int>>> adj[100001];
unordered_map<int, int> D[100001];
unordered_map<int, int> sum[100001];
map<int, pair<int, int>> edge[100001];
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("TEST.in", "r", stdin);
//freopen("TEST.out", "w", stdout);
int n, m;
cin >> n >> m;
map<int, vector<pair<int, int>>> test;
for (int i = 0; i < m; i++)
{
int u, v, c, w;
cin >> u >> v >> c >> w;
adj[u][c].emplace_back(v, w);
adj[v][c].emplace_back(u, w);
sum[u][c] += w;
sum[v][c] += w;
edge[u][v] = {c, w};
edge[v][u] = {c, w};
}
D[1][0] = 1;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;
q.push({1, 1, 0});
while (!q.empty())
{
int d = q.top()[0];
int u = q.top()[1];
int t = q.top()[2];
//cerr << u << " " << t << " " << d - 1 << endl;
int pc, pw;
if (t == 0) tie(pc, pw) = make_pair(-1, 0);
else tie(pc, pw) = edge[u][t];
q.pop();
for (const auto& [c, l] : adj[u])
{
int sz = (int)l.size();
int s = sum[u][c];
if (pc == c)
{
sz--;
s -= pw;
}
for (const auto& [v, w] : l)
{
if (v == t) continue;
if (D[u][t] + w < D[v][u] || !D[v][u])
{
D[v][u] = D[u][t] + w;
q.push({D[v][u], v, u});
}
/*if (sz == 1 && (D[u][t] < D[v][u] || !D[v][u]))
{
D[v][u] = D[u][t];
q.push({D[v][u], v, u});
}*/
if (D[u][t] + s - w < D[v][0] || !D[v][0])
{
D[v][0] = D[u][t] + s - w;
q.push({D[v][0], v, 0});
}
}
}
}
int ans = (int)1e18;
for (const auto& [t, dis] : D[n]) ans = min(ans, dis);
if (ans == (int)1e18) cout << -1;
else cout << ans - 1;
return 0;
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:35:13: warning: unused variable 'd' [-Wunused-variable]
35 | int d = q.top()[0];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
20568 KB |
Output is correct |
2 |
Correct |
6 ms |
20572 KB |
Output is correct |
3 |
Correct |
5 ms |
20572 KB |
Output is correct |
4 |
Correct |
5 ms |
20812 KB |
Output is correct |
5 |
Correct |
6 ms |
20808 KB |
Output is correct |
6 |
Correct |
5 ms |
20572 KB |
Output is correct |
7 |
Correct |
9 ms |
21084 KB |
Output is correct |
8 |
Correct |
7 ms |
20828 KB |
Output is correct |
9 |
Correct |
88 ms |
21852 KB |
Output is correct |
10 |
Correct |
57 ms |
21848 KB |
Output is correct |
11 |
Correct |
67 ms |
21596 KB |
Output is correct |
12 |
Correct |
29 ms |
21592 KB |
Output is correct |
13 |
Correct |
76 ms |
21596 KB |
Output is correct |
14 |
Correct |
69 ms |
21592 KB |
Output is correct |
15 |
Correct |
8 ms |
21340 KB |
Output is correct |
16 |
Correct |
10 ms |
21536 KB |
Output is correct |
17 |
Correct |
9 ms |
21340 KB |
Output is correct |
18 |
Correct |
6 ms |
21076 KB |
Output is correct |
19 |
Correct |
16 ms |
21340 KB |
Output is correct |
20 |
Correct |
8 ms |
21404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
445 ms |
60572 KB |
Output is correct |
2 |
Correct |
158 ms |
38576 KB |
Output is correct |
3 |
Correct |
950 ms |
70528 KB |
Output is correct |
4 |
Correct |
243 ms |
46628 KB |
Output is correct |
5 |
Execution timed out |
3075 ms |
118004 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
20568 KB |
Output is correct |
2 |
Correct |
6 ms |
20572 KB |
Output is correct |
3 |
Correct |
5 ms |
20572 KB |
Output is correct |
4 |
Correct |
5 ms |
20812 KB |
Output is correct |
5 |
Correct |
6 ms |
20808 KB |
Output is correct |
6 |
Correct |
5 ms |
20572 KB |
Output is correct |
7 |
Correct |
9 ms |
21084 KB |
Output is correct |
8 |
Correct |
7 ms |
20828 KB |
Output is correct |
9 |
Correct |
88 ms |
21852 KB |
Output is correct |
10 |
Correct |
57 ms |
21848 KB |
Output is correct |
11 |
Correct |
67 ms |
21596 KB |
Output is correct |
12 |
Correct |
29 ms |
21592 KB |
Output is correct |
13 |
Correct |
76 ms |
21596 KB |
Output is correct |
14 |
Correct |
69 ms |
21592 KB |
Output is correct |
15 |
Correct |
8 ms |
21340 KB |
Output is correct |
16 |
Correct |
10 ms |
21536 KB |
Output is correct |
17 |
Correct |
9 ms |
21340 KB |
Output is correct |
18 |
Correct |
6 ms |
21076 KB |
Output is correct |
19 |
Correct |
16 ms |
21340 KB |
Output is correct |
20 |
Correct |
8 ms |
21404 KB |
Output is correct |
21 |
Correct |
445 ms |
60572 KB |
Output is correct |
22 |
Correct |
158 ms |
38576 KB |
Output is correct |
23 |
Correct |
950 ms |
70528 KB |
Output is correct |
24 |
Correct |
243 ms |
46628 KB |
Output is correct |
25 |
Execution timed out |
3075 ms |
118004 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |