//直接抄解,因為我笨
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fs first
#define sc second
int n, m;
int vis[510000] = {0}, dis[510000];
vector< pair<int,pii> > e[510000];
vector< pii > ne[510000];
signed main () {
//輸入
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c, k;
cin >> a >> b >> c >> k;
e[a] . push_back({c,{b,k}});
e[b] . push_back({c,{a,k}});
}
//建圖
int now = n + 1;
for (int i = 1; i <= n; i++) {
//操作1
for (auto [c, p] : e[i]) ne[i] . push_back(p);
//操作2、先操作1再操作2
map<int, vector<pii>>mp;
for (auto [c, p] : e[i]) mp[c] . push_back(p);
for (auto [c, vv] : mp) {
++now;
int sum = 0;
for (auto [j, w] : vv) sum += w;
for (auto [j, w] : vv) {
//操作2
ne[i] . push_back({j, sum - w});
//先1再2
ne[now] . push_back({j, sum - w});
ne[j] . push_back({now, 0});
}
}
}
// Dijkstra and output
memset(dis, 63, sizeof(dis));
int inf = dis[0];
dis[1] = 0;
priority_queue< pii, vector<pii>, greater<pii> > pq;
pq.push({0, 1});
while (pq.size()) {
auto [wow, i] = pq.top();
pq.pop();
if (vis[i]) continue;
vis[i] = 1;
for (auto [j, w] : ne[i]) {
if (dis[i] + w < dis[j]) {
dis[j] = dis[i] + w;
pq.push({dis[j], j});
}
}
}
if (dis[n] >= inf / 2) dis[n] = -1;
cout << dis[n] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
29276 KB |
Output is correct |
2 |
Correct |
6 ms |
29276 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
7 ms |
29272 KB |
Output is correct |
5 |
Correct |
7 ms |
29276 KB |
Output is correct |
6 |
Correct |
7 ms |
29272 KB |
Output is correct |
7 |
Correct |
7 ms |
29532 KB |
Output is correct |
8 |
Correct |
7 ms |
29528 KB |
Output is correct |
9 |
Correct |
8 ms |
29788 KB |
Output is correct |
10 |
Correct |
8 ms |
29788 KB |
Output is correct |
11 |
Correct |
11 ms |
29816 KB |
Output is correct |
12 |
Correct |
8 ms |
29788 KB |
Output is correct |
13 |
Correct |
8 ms |
29788 KB |
Output is correct |
14 |
Correct |
9 ms |
29756 KB |
Output is correct |
15 |
Correct |
7 ms |
29532 KB |
Output is correct |
16 |
Correct |
8 ms |
29788 KB |
Output is correct |
17 |
Correct |
8 ms |
29816 KB |
Output is correct |
18 |
Correct |
7 ms |
29528 KB |
Output is correct |
19 |
Correct |
8 ms |
29788 KB |
Output is correct |
20 |
Correct |
9 ms |
29788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
52052 KB |
Output is correct |
2 |
Correct |
46 ms |
40136 KB |
Output is correct |
3 |
Correct |
110 ms |
66736 KB |
Output is correct |
4 |
Correct |
66 ms |
44748 KB |
Output is correct |
5 |
Correct |
344 ms |
93740 KB |
Output is correct |
6 |
Correct |
262 ms |
89168 KB |
Output is correct |
7 |
Correct |
178 ms |
85884 KB |
Output is correct |
8 |
Correct |
272 ms |
87128 KB |
Output is correct |
9 |
Correct |
303 ms |
87360 KB |
Output is correct |
10 |
Correct |
158 ms |
65220 KB |
Output is correct |
11 |
Correct |
102 ms |
57104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
29276 KB |
Output is correct |
2 |
Correct |
6 ms |
29276 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
7 ms |
29272 KB |
Output is correct |
5 |
Correct |
7 ms |
29276 KB |
Output is correct |
6 |
Correct |
7 ms |
29272 KB |
Output is correct |
7 |
Correct |
7 ms |
29532 KB |
Output is correct |
8 |
Correct |
7 ms |
29528 KB |
Output is correct |
9 |
Correct |
8 ms |
29788 KB |
Output is correct |
10 |
Correct |
8 ms |
29788 KB |
Output is correct |
11 |
Correct |
11 ms |
29816 KB |
Output is correct |
12 |
Correct |
8 ms |
29788 KB |
Output is correct |
13 |
Correct |
8 ms |
29788 KB |
Output is correct |
14 |
Correct |
9 ms |
29756 KB |
Output is correct |
15 |
Correct |
7 ms |
29532 KB |
Output is correct |
16 |
Correct |
8 ms |
29788 KB |
Output is correct |
17 |
Correct |
8 ms |
29816 KB |
Output is correct |
18 |
Correct |
7 ms |
29528 KB |
Output is correct |
19 |
Correct |
8 ms |
29788 KB |
Output is correct |
20 |
Correct |
9 ms |
29788 KB |
Output is correct |
21 |
Correct |
93 ms |
52052 KB |
Output is correct |
22 |
Correct |
46 ms |
40136 KB |
Output is correct |
23 |
Correct |
110 ms |
66736 KB |
Output is correct |
24 |
Correct |
66 ms |
44748 KB |
Output is correct |
25 |
Correct |
344 ms |
93740 KB |
Output is correct |
26 |
Correct |
262 ms |
89168 KB |
Output is correct |
27 |
Correct |
178 ms |
85884 KB |
Output is correct |
28 |
Correct |
272 ms |
87128 KB |
Output is correct |
29 |
Correct |
303 ms |
87360 KB |
Output is correct |
30 |
Correct |
158 ms |
65220 KB |
Output is correct |
31 |
Correct |
102 ms |
57104 KB |
Output is correct |
32 |
Correct |
115 ms |
69912 KB |
Output is correct |
33 |
Correct |
106 ms |
64204 KB |
Output is correct |
34 |
Correct |
207 ms |
70700 KB |
Output is correct |
35 |
Correct |
188 ms |
63688 KB |
Output is correct |
36 |
Correct |
166 ms |
67028 KB |
Output is correct |
37 |
Correct |
182 ms |
75980 KB |
Output is correct |
38 |
Correct |
235 ms |
91820 KB |
Output is correct |
39 |
Correct |
120 ms |
81552 KB |
Output is correct |
40 |
Correct |
301 ms |
88492 KB |
Output is correct |
41 |
Correct |
331 ms |
89328 KB |
Output is correct |
42 |
Correct |
291 ms |
83112 KB |
Output is correct |
43 |
Correct |
108 ms |
57376 KB |
Output is correct |
44 |
Correct |
169 ms |
86624 KB |
Output is correct |
45 |
Correct |
272 ms |
73808 KB |
Output is correct |
46 |
Correct |
195 ms |
75344 KB |
Output is correct |
47 |
Correct |
205 ms |
72172 KB |
Output is correct |
48 |
Correct |
359 ms |
96976 KB |
Output is correct |