#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int c[200000];
int p[200000];
vector<pair<int, pair<int, int> > > adj[100000];
vector<ll> d;
bool visited[100000];
void dijkstra() {
d.assign(n, LONG_LONG_MAX);
priority_queue<pair<ll, int> > q;
d[0] = 0;
q.push(make_pair(0, 0));
while(!q.empty()) {
int v = q.top().second;
q.pop();
if(visited[v]) continue;
visited[v] = true;
set<int> s;
for(auto u : adj[v]) {
s.insert(u.second.first);
}
vector<int> v1;
vector<ll> v2;
vector<ll> v3;
while(!s.empty()) {
v1.push_back(*s.begin());
s.erase(*s.begin());
v2.push_back(0);
v3.push_back(2000000000000000);
}
for(auto u : adj[v]) {
int l = lower_bound(v1.begin(), v1.end(), u.second.first) - v1.begin();
v2[l] += (ll) u.second.second;
v3[l] = min(v3[l], d[u.first]);
}
for(auto u : adj[v]) {
if(visited[u.first]) continue;
int l = lower_bound(v1.begin(), v1.end(), u.second.first) - v1.begin();
d[u.first] = min(d[u.first], d[v] + ((ll) u.second.second));
d[u.first] = min(d[u.first], v3[l] + v2[l] - ((ll) u.second.second));
d[u.first] = min(d[u.first], d[v] + v2[l] - ((ll) u.second.second));
q.push(make_pair(-d[u.first], u.first));
}
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++) {
int a, b, color, cost;
cin >> a >> b >> color >> cost;
a--; b--;
adj[a].push_back(make_pair(b, make_pair(color, cost)));
adj[b].push_back(make_pair(a, make_pair(color, cost)));
}
dijkstra();
if(d[n-1] != LONG_LONG_MAX) cout << d[n-1] << endl;
else cout << -1 << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2656 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2656 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2804 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 12 |
Correct |
3 ms |
2720 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2672 KB |
Output is correct |
| 16 |
Correct |
5 ms |
2800 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2672 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
5 ms |
2796 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
113 ms |
8680 KB |
Output is correct |
| 2 |
Correct |
48 ms |
5176 KB |
Output is correct |
| 3 |
Correct |
185 ms |
11848 KB |
Output is correct |
| 4 |
Correct |
85 ms |
6512 KB |
Output is correct |
| 5 |
Correct |
360 ms |
19692 KB |
Output is correct |
| 6 |
Correct |
307 ms |
17928 KB |
Output is correct |
| 7 |
Correct |
286 ms |
16024 KB |
Output is correct |
| 8 |
Correct |
270 ms |
15636 KB |
Output is correct |
| 9 |
Correct |
294 ms |
15868 KB |
Output is correct |
| 10 |
Correct |
176 ms |
11476 KB |
Output is correct |
| 11 |
Correct |
114 ms |
9100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2656 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2656 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2804 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 12 |
Correct |
3 ms |
2720 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2772 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2672 KB |
Output is correct |
| 16 |
Correct |
5 ms |
2800 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2672 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
5 ms |
2796 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 21 |
Correct |
113 ms |
8680 KB |
Output is correct |
| 22 |
Correct |
48 ms |
5176 KB |
Output is correct |
| 23 |
Correct |
185 ms |
11848 KB |
Output is correct |
| 24 |
Correct |
85 ms |
6512 KB |
Output is correct |
| 25 |
Correct |
360 ms |
19692 KB |
Output is correct |
| 26 |
Correct |
307 ms |
17928 KB |
Output is correct |
| 27 |
Correct |
286 ms |
16024 KB |
Output is correct |
| 28 |
Correct |
270 ms |
15636 KB |
Output is correct |
| 29 |
Correct |
294 ms |
15868 KB |
Output is correct |
| 30 |
Correct |
176 ms |
11476 KB |
Output is correct |
| 31 |
Correct |
114 ms |
9100 KB |
Output is correct |
| 32 |
Correct |
201 ms |
13636 KB |
Output is correct |
| 33 |
Correct |
169 ms |
11380 KB |
Output is correct |
| 34 |
Correct |
240 ms |
14444 KB |
Output is correct |
| 35 |
Correct |
182 ms |
11860 KB |
Output is correct |
| 36 |
Correct |
174 ms |
10664 KB |
Output is correct |
| 37 |
Correct |
227 ms |
14924 KB |
Output is correct |
| 38 |
Correct |
255 ms |
17800 KB |
Output is correct |
| 39 |
Correct |
248 ms |
14716 KB |
Output is correct |
| 40 |
Correct |
323 ms |
17040 KB |
Output is correct |
| 41 |
Correct |
317 ms |
17132 KB |
Output is correct |
| 42 |
Correct |
297 ms |
16440 KB |
Output is correct |
| 43 |
Correct |
132 ms |
10360 KB |
Output is correct |
| 44 |
Correct |
295 ms |
17836 KB |
Output is correct |
| 45 |
Correct |
242 ms |
13640 KB |
Output is correct |
| 46 |
Correct |
209 ms |
12836 KB |
Output is correct |
| 47 |
Correct |
239 ms |
12684 KB |
Output is correct |
| 48 |
Correct |
419 ms |
20396 KB |
Output is correct |
