#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e18;
const int BASE = 1337;
struct toData {
ll v, C, P, eid;
};
struct DataE {
ll u, v, C, P;
};
int n, m;
map<int, ll> dp[N];
DataE Edge[N];
vector<toData> ke[N];
int color[N];
ll costcol[N];
void solution () {
cin >> n >> m;
rep (i, 1, m) {
ll u, v, C, P;
cin >> u >> v >> C >> P;
Edge[i] = {u, v, C, P};
ke[u].push_back({v, C, P, i});
ke[v].push_back({u, C, P, i});
color[i] = C;
}
if (m == 1) {
bool ok = 0;
rep (i, 1, m) {
if (Edge[i].u == 1 && Edge[i].v == n) ok = 1;
}
if (ok) cout << 0 <<"\n";
else cout << -1 <<"\n";
return;
}
rep (i, 1, n) {
sort (ALL(ke[i]), [] (toData A, toData B) {return A.eid < B.eid; });
}
struct Data {
ll u, eid, w;
};
struct cmp {
bool operator () (Data A, Data B) { return A.w > B.w; }
};
rep (i, 1, n) {
dp[i][0] = INF;
iter (&id, ke[i]) dp[i][id.eid] = INF;
}
priority_queue<Data, vector<Data>, cmp> pq;
pq.push({1, 0, 0});
dp[1][0] = 0;
while (!pq.empty()) {
ll u = pq.top().u, ueid = pq.top().eid;
pq.pop();
static set<int> curcol;
iter (&id, curcol) costcol[id] = 0;
curcol.clear();
iter (&id, ke[u]) {
curcol.insert(id.C);
costcol[id.C] += id.P;
}
iter (&id, ke[u]) {
ll v = id.v, C = id.C, p = id.P, toid = id.eid;
if (dp[v][0] > dp[u][ueid] + costcol[id.C] - id.P - (id.C == color[ueid]) * Edge[ueid].P) {
dp[v][0] = dp[u][ueid] + costcol[id.C] - id.P - (id.C == color[ueid]) * Edge[ueid].P;
pq.push({v, 0, dp[v][0]});
}
if (SZ(curcol) < m) {
if (dp[v][toid] > dp[u][ueid] + id.P) {
dp[v][toid] = dp[u][ueid] + id.P;
pq.push({v, toid, dp[v][toid]});
}
}
}
}
ll res = dp[n][0];
iter (&id, ke[n]) res = min(res, dp[n][id.eid]);
if (res != INF) cout << res <<"\n";
else cout << -1 <<"\n";
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13
*/
Compilation message
Main.cpp: In function 'void solution()':
Main.cpp:88:26: warning: unused variable 'C' [-Wunused-variable]
88 | ll v = id.v, C = id.C, p = id.P, toid = id.eid;
| ^
Main.cpp:88:36: warning: unused variable 'p' [-Wunused-variable]
88 | ll v = id.v, C = id.C, p = id.P, toid = id.eid;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
2 ms |
9560 KB |
Output is correct |
4 |
Correct |
2 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9564 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
6 ms |
9880 KB |
Output is correct |
8 |
Correct |
4 ms |
9564 KB |
Output is correct |
9 |
Correct |
129 ms |
10076 KB |
Output is correct |
10 |
Correct |
98 ms |
10188 KB |
Output is correct |
11 |
Correct |
72 ms |
10072 KB |
Output is correct |
12 |
Correct |
25 ms |
10076 KB |
Output is correct |
13 |
Correct |
72 ms |
10328 KB |
Output is correct |
14 |
Correct |
87 ms |
10328 KB |
Output is correct |
15 |
Correct |
3 ms |
9816 KB |
Output is correct |
16 |
Correct |
5 ms |
10076 KB |
Output is correct |
17 |
Correct |
5 ms |
9820 KB |
Output is correct |
18 |
Correct |
3 ms |
9564 KB |
Output is correct |
19 |
Correct |
21 ms |
10236 KB |
Output is correct |
20 |
Correct |
4 ms |
9816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
301 ms |
37568 KB |
Output is correct |
2 |
Correct |
102 ms |
21572 KB |
Output is correct |
3 |
Runtime error |
50 ms |
42836 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
2 ms |
9560 KB |
Output is correct |
4 |
Correct |
2 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9564 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
6 ms |
9880 KB |
Output is correct |
8 |
Correct |
4 ms |
9564 KB |
Output is correct |
9 |
Correct |
129 ms |
10076 KB |
Output is correct |
10 |
Correct |
98 ms |
10188 KB |
Output is correct |
11 |
Correct |
72 ms |
10072 KB |
Output is correct |
12 |
Correct |
25 ms |
10076 KB |
Output is correct |
13 |
Correct |
72 ms |
10328 KB |
Output is correct |
14 |
Correct |
87 ms |
10328 KB |
Output is correct |
15 |
Correct |
3 ms |
9816 KB |
Output is correct |
16 |
Correct |
5 ms |
10076 KB |
Output is correct |
17 |
Correct |
5 ms |
9820 KB |
Output is correct |
18 |
Correct |
3 ms |
9564 KB |
Output is correct |
19 |
Correct |
21 ms |
10236 KB |
Output is correct |
20 |
Correct |
4 ms |
9816 KB |
Output is correct |
21 |
Correct |
301 ms |
37568 KB |
Output is correct |
22 |
Correct |
102 ms |
21572 KB |
Output is correct |
23 |
Runtime error |
50 ms |
42836 KB |
Execution killed with signal 11 |
24 |
Halted |
0 ms |
0 KB |
- |