#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int N = 100100;
const int M = 200100;
int n, m;
vector<tuple<int, int, int>> adj[N];
int last[M]; // last node that had an edge with this color
int ccnt[M]; // for current node, how many edges with this color
ll csum[M]; // for current node, sum of weights of edges with this color
void process_color(int c, int w, int u) {
if (last[c] != u) {
last[c] = u;
ccnt[c] = 1;
csum[c] = w;
} else {
ccnt[c] += 1;
csum[c] += w;
}
}
ll dijkstra(int src) {
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
static ll dist[N];
for (int i = 1; i <= n; ++i) {
dist[i] = inf;
}
for (int i = 0; i < m; ++i) {
last[i] = -1;
}
dist[src] = 0;
pq.emplace(0, src);
while (!pq.empty()) {
ll cur_dist;
int u;
tie(cur_dist, u) = pq.top();
pq.pop();
if (cur_dist != dist[u]) continue;
for (auto& to : adj[u]) {
int c, w;
tie(ignore, c, w) = to;
process_color(c, w, u);
}
for (auto& to : adj[u]) {
int v, c, w;
tie(v, c, w) = to;
// in case there is more than 1 edge with color c:
// either change the color of this edge (cost: w)
// or all others (cost: csum[c] - w)
// since 1 <= c <= M and degree[u] < M,
// we can always change the edges to some color
// that won't interfere in future operations
// also, we can change edges like this because
// all edges adjacent to u won't be crossed ever again
ll alt = dist[u] + min((ll)w, csum[c]-w);
if (alt < dist[v]) {
dist[v] = alt;
pq.emplace(alt, v);
}
}
}
return dist[n] == inf ? -1 : dist[n];
}
ll solve_star(int center) {
// center has a degree of M
// special measures must be taken
for (int c = 0; c < m; ++c) {
last[c] = -1;
}
int c1, cn;
ll w1, wn;
for (auto& to : adj[center]) {
int v, c, w;
tie(v, c, w) = to;
process_color(c, w, center);
if (v == 1) {
w1 = w;
c1 = c;
} else if (v == n) {
wn = w;
cn = w;
}
}
if (center == 1) {
return min(wn, csum[cn]-wn);
} else if (center == n) {
return min(w1, csum[c1]-w1);
} else if (c1 == cn) {
return min(w1+wn, min(csum[c1]-w1, csum[c1]-wn));
} else {
return min(w1, csum[c1]-w1) + min(wn, csum[cn]-wn);
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b, c, w;
cin >> a >> b >> c >> w;
adj[a].emplace_back(b, c, w);
adj[b].emplace_back(a, c, w);
}
for (int u = 1; u <= n; ++u) {
if (adj[u].size() == m) {
cout << solve_star(u) << '\n';
return 0;
}
}
cout << dijkstra(1) << '\n';
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:113:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
113 | if (adj[u].size() == m) {
| ~~~~~~~~~~~~~~^~~~
Main.cpp: In function 'll solve_star(int)':
Main.cpp:79:9: warning: 'wn' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | ll w1, wn;
| ^~
Main.cpp:79:5: warning: 'w1' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | ll w1, wn;
| ^~
Main.cpp:99:48: warning: 'cn' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | return min(w1, csum[c1]-w1) + min(wn, csum[cn]-wn);
| ~~~~~~~^
Main.cpp:78:6: warning: 'c1' may be used uninitialized in this function [-Wmaybe-uninitialized]
78 | int c1, cn;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
51 ms |
8036 KB |
Output is correct |
| 2 |
Correct |
22 ms |
5040 KB |
Output is correct |
| 3 |
Correct |
76 ms |
11408 KB |
Output is correct |
| 4 |
Correct |
36 ms |
6296 KB |
Output is correct |
| 5 |
Incorrect |
142 ms |
16236 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
