#include <bits/stdc++.h>
#define int long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms (a); memset (a, 0, sizeof a);
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
using namespace std;
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 4e5 + 10;
int n, m, d[400005];
vector <int> a;
vector <pair <int, int> > g[400005];
vector <pair <int, pair <int, int> > > v[400005];
signed main () {
// freopen ("10.in", "r", stdin);
cin >> n >> m;
re (i, 0, m - 1, 1) {
int a, b, c, p;
cin >> a >> b >> c >> p;
v[a].push_back ({c, {p, b}});
v[b].push_back ({c, {p, a}});
}
int sz = n;
for (int i = 1; i < n; i++) {
if (v[i].empty()) continue;
sort (v[i].begin(), v[i].end());
for (int l = 0, r = 0; l < v[i].size(); l = r) {
lint s = 0;
while (r < v[i].size() && v[i][l].first == v[i][r].first) s += v[i][r++].second.first;
if (r - l == 1) g[i].emplace_back (0, v[i][l].second.second);
else {
g[i].emplace_back (0, ++sz);
for (int j = l; j < r; j++) {
pint x = v[i][j].second;
g[i].emplace_back (x);
g[x.second].emplace_back (0, sz);
g[sz].emplace_back (s - x.first, x.second);
}
}
}
}
priority_queue<pair <int, int> > Q;
Q.emplace (0, 1);
for (int i = 1; i <= sz; i++) d[i] = 4e18;
while (!Q.empty()) {
auto t = Q.top();
Q.pop();
if (d[t.second] != 4e18) continue;
d[t.second] = -t.first;
for (auto nxt : g[t.second]) Q.emplace (t.first - nxt.first, nxt.second);
}
cout << (d[n] == 4e18 ? -1 : d[n]);
}
Compilation message
robot.cpp: In function 'int main()':
robot.cpp:32:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int l = 0, r = 0; l < v[i].size(); l = r) {
| ~~^~~~~~~~~~~~~
robot.cpp:34:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (r < v[i].size() && v[i][l].first == v[i][r].first) s += v[i][r++].second.first;
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
19924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
21972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
19124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
76 ms |
26180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
