#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <ctime>
#include <queue>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll MOD = 1e9 + 7, MX2 = 1e6, SZ = 1e6 + 100, INF = 1e9 * 1e9 + 100;
ll n, m;
struct edge {
ll to, c, p, ind;
};
vector<vector<edge>> gr;
set<tuple<ll, ll, ll>> dists; // dist, v, col
map<pair<ll, ll>, ll> sv;
map<pair<ll, ll>, ll> cnt;
vector<map<ll, vector<ll>>> cols;
signed main() {
fastInp;
cin >> n >> m;
gr.resize(n);
cols.resize(n);
dists.insert({ 0, 0, 0 });
for (int i = 1; i < n; i++) dists.insert({ INF, i, 0 });
for (int i = 0; i < m; i++) {
ll u, v, c, p;
cin >> u >> v >> c >> p;
u--; v--;
gr[u].push_back({ v, c, p, gr[v].size() });
gr[v].push_back({ u, c, p, gr[u].size() - 1 });
cols[u][c].push_back(gr[u].size() - 1);
cols[v][c].push_back(gr[v].size() - 1);
dists.insert({ INF, u, c });
dists.insert({ INF, v, c });
cnt[{v, c}] += p;
cnt[{u, c}] += p;
}
for (auto c : dists) sv[{get<1>(c), get<2>(c)}] = get<0>(c);
ll ds = INF;
while (!dists.empty()) {
tuple<ll, ll, ll> cur = (*dists.begin());
dists.erase(dists.begin());
ll d = get<0>(cur);
ll v = get<1>(cur);
ll c = get<2>(cur);
if (v == n - 1 && c == 0) {
ds = d;
break;
}
if (c == 0) {
for (auto e : gr[v]) {
if (sv[{e.to, 0}] > d + e.p) {
dists.erase({ sv[{e.to, 0}], e.to, 0 });
sv[{e.to, 0}] = d + e.p;
dists.insert({ sv[{e.to, 0}], e.to, 0 });
}
if (sv[{e.to, 0}] > d + cnt[{v, e.c}] - e.p) {
dists.erase({ sv[{e.to, 0}], e.to, 0 });
sv[{e.to, 0}] = d + cnt[{v, e.c}] - e.p;
dists.insert({ sv[{e.to, 0}], e.to, 0 });
}
}
for (auto e : gr[v]) {
if (sv[{e.to, e.c}] > d) {
dists.erase({ sv[{e.to, e.c}], e.to, e.c });
sv[{e.to, e.c}] = d;
dists.insert({ sv[{e.to, e.c}], e.to, e.c });
}
}
}
else {
for (auto ind : cols[v][c]) {
edge e = gr[v][ind];
if (sv[{e.to, 0}] > d + cnt[{v, e.c}] - e.p) {
dists.erase({ sv[{e.to, 0}], e.to, 0 });
sv[{e.to, 0}] = d + cnt[{v, e.c}] - e.p;
dists.insert({ sv[{e.to, 0}], e.to, 0 });
}
}
}
}
ll a = ds;
if (a == INF) {
cout << "-1";
}
else {
cout << a;
}
return 0;
}
/*
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
5 2
1 4 1 2
3 5 1 4
5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:45:46: warning: narrowing conversion of '(& gr.std::vector<std::vector<edge> >::operator[](((std::vector<std::vector<edge> >::size_type)v)))->std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
45 | gr[u].push_back({ v, c, p, gr[v].size() });
| ~~~~~~~~~~^~
Main.cpp:46:49: warning: narrowing conversion of '((& gr.std::vector<std::vector<edge> >::operator[](((std::vector<std::vector<edge> >::size_type)u)))->std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'll' {aka 'long long int'} [-Wnarrowing]
46 | gr[v].push_back({ u, c, p, gr[u].size() - 1 });
| ~~~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
3 ms |
620 KB |
Output is correct |
8 |
Correct |
3 ms |
492 KB |
Output is correct |
9 |
Correct |
11 ms |
1516 KB |
Output is correct |
10 |
Correct |
14 ms |
1388 KB |
Output is correct |
11 |
Correct |
8 ms |
1004 KB |
Output is correct |
12 |
Correct |
8 ms |
1004 KB |
Output is correct |
13 |
Correct |
7 ms |
1004 KB |
Output is correct |
14 |
Correct |
7 ms |
1004 KB |
Output is correct |
15 |
Correct |
6 ms |
876 KB |
Output is correct |
16 |
Correct |
9 ms |
1132 KB |
Output is correct |
17 |
Correct |
9 ms |
1004 KB |
Output is correct |
18 |
Correct |
3 ms |
876 KB |
Output is correct |
19 |
Correct |
5 ms |
876 KB |
Output is correct |
20 |
Correct |
6 ms |
1004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1035 ms |
34412 KB |
Output is correct |
2 |
Correct |
399 ms |
18156 KB |
Output is correct |
3 |
Correct |
754 ms |
31596 KB |
Output is correct |
4 |
Correct |
589 ms |
24428 KB |
Output is correct |
5 |
Execution timed out |
3075 ms |
113236 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
3 ms |
620 KB |
Output is correct |
8 |
Correct |
3 ms |
492 KB |
Output is correct |
9 |
Correct |
11 ms |
1516 KB |
Output is correct |
10 |
Correct |
14 ms |
1388 KB |
Output is correct |
11 |
Correct |
8 ms |
1004 KB |
Output is correct |
12 |
Correct |
8 ms |
1004 KB |
Output is correct |
13 |
Correct |
7 ms |
1004 KB |
Output is correct |
14 |
Correct |
7 ms |
1004 KB |
Output is correct |
15 |
Correct |
6 ms |
876 KB |
Output is correct |
16 |
Correct |
9 ms |
1132 KB |
Output is correct |
17 |
Correct |
9 ms |
1004 KB |
Output is correct |
18 |
Correct |
3 ms |
876 KB |
Output is correct |
19 |
Correct |
5 ms |
876 KB |
Output is correct |
20 |
Correct |
6 ms |
1004 KB |
Output is correct |
21 |
Correct |
1035 ms |
34412 KB |
Output is correct |
22 |
Correct |
399 ms |
18156 KB |
Output is correct |
23 |
Correct |
754 ms |
31596 KB |
Output is correct |
24 |
Correct |
589 ms |
24428 KB |
Output is correct |
25 |
Execution timed out |
3075 ms |
113236 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |