/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;
struct Edge{
int nxt, c; ll e;
};
int n, m;
ll dist[N][2];
vector<Edge> g[N];
map<int, ll> s[N];
void solve(){
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u, v, c, p; cin >> u >> v >> c >> p;
g[u].pb({v, c, p});
g[v].pb({u, c, p});
s[u][c] += p;
s[v][c] += p;
}
for(int i = 1; i <= n; ++i) dist[i][0] = dist[i][1] = 1e18;
priority_queue<array<ll, 3>> q;
vector<bool> vis[2]; vis[0].resize(n+1), vis[1].resize(n+1);
dist[n][0] = 0;
q.push({0, n, -1});
while(!q.empty()){
int v = q.top()[1], cc = q.top()[2];
ll D = -q.top()[0];
q.pop();
if(vis[cc == -1][v]) continue;
vis[cc == -1][v] = 1;
// cout << v << '\n';
for(auto E: g[v]){
int u = E.nxt, c = E.c; ll e = E.e;
ll val = s[u][c];
if(cc == c) e = 0;
if(D + e < dist[u][0]){
dist[u][0] = D + e;
q.push({-dist[u][0], u, -1});
}
if(e > 0 && D + val - e < dist[u][1]){
dist[u][1] = D + val - e;
q.push({-dist[u][1], u, c});
}
}
}
if(min(dist[1][0], dist[1][1]) == 1e18) cout << -1;
else cout << min(dist[1][0], dist[1][1]);
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int T = 1, aa;
// cin >> T;aa=T;
while(T--){
// cout << "Case #" << aa-T << ": ";
solve();
cout << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:75:16: warning: unused variable 'aa' [-Wunused-variable]
75 | int T = 1, aa;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
70740 KB |
Output is correct |
2 |
Correct |
34 ms |
70720 KB |
Output is correct |
3 |
Correct |
42 ms |
70688 KB |
Output is correct |
4 |
Correct |
35 ms |
70768 KB |
Output is correct |
5 |
Correct |
39 ms |
70784 KB |
Output is correct |
6 |
Correct |
32 ms |
70716 KB |
Output is correct |
7 |
Correct |
32 ms |
70804 KB |
Output is correct |
8 |
Correct |
33 ms |
70764 KB |
Output is correct |
9 |
Correct |
34 ms |
71088 KB |
Output is correct |
10 |
Correct |
35 ms |
71124 KB |
Output is correct |
11 |
Correct |
34 ms |
70996 KB |
Output is correct |
12 |
Correct |
37 ms |
70920 KB |
Output is correct |
13 |
Correct |
40 ms |
71028 KB |
Output is correct |
14 |
Correct |
35 ms |
70988 KB |
Output is correct |
15 |
Correct |
34 ms |
70812 KB |
Output is correct |
16 |
Correct |
34 ms |
70960 KB |
Output is correct |
17 |
Correct |
36 ms |
70868 KB |
Output is correct |
18 |
Correct |
37 ms |
70876 KB |
Output is correct |
19 |
Correct |
35 ms |
70960 KB |
Output is correct |
20 |
Correct |
37 ms |
70928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
147 ms |
81104 KB |
Output is correct |
2 |
Correct |
70 ms |
75976 KB |
Output is correct |
3 |
Correct |
145 ms |
82744 KB |
Output is correct |
4 |
Correct |
98 ms |
77440 KB |
Output is correct |
5 |
Correct |
520 ms |
105216 KB |
Output is correct |
6 |
Correct |
429 ms |
99320 KB |
Output is correct |
7 |
Correct |
260 ms |
95716 KB |
Output is correct |
8 |
Correct |
292 ms |
89468 KB |
Output is correct |
9 |
Correct |
301 ms |
89524 KB |
Output is correct |
10 |
Correct |
168 ms |
86104 KB |
Output is correct |
11 |
Correct |
117 ms |
81708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
70740 KB |
Output is correct |
2 |
Correct |
34 ms |
70720 KB |
Output is correct |
3 |
Correct |
42 ms |
70688 KB |
Output is correct |
4 |
Correct |
35 ms |
70768 KB |
Output is correct |
5 |
Correct |
39 ms |
70784 KB |
Output is correct |
6 |
Correct |
32 ms |
70716 KB |
Output is correct |
7 |
Correct |
32 ms |
70804 KB |
Output is correct |
8 |
Correct |
33 ms |
70764 KB |
Output is correct |
9 |
Correct |
34 ms |
71088 KB |
Output is correct |
10 |
Correct |
35 ms |
71124 KB |
Output is correct |
11 |
Correct |
34 ms |
70996 KB |
Output is correct |
12 |
Correct |
37 ms |
70920 KB |
Output is correct |
13 |
Correct |
40 ms |
71028 KB |
Output is correct |
14 |
Correct |
35 ms |
70988 KB |
Output is correct |
15 |
Correct |
34 ms |
70812 KB |
Output is correct |
16 |
Correct |
34 ms |
70960 KB |
Output is correct |
17 |
Correct |
36 ms |
70868 KB |
Output is correct |
18 |
Correct |
37 ms |
70876 KB |
Output is correct |
19 |
Correct |
35 ms |
70960 KB |
Output is correct |
20 |
Correct |
37 ms |
70928 KB |
Output is correct |
21 |
Correct |
147 ms |
81104 KB |
Output is correct |
22 |
Correct |
70 ms |
75976 KB |
Output is correct |
23 |
Correct |
145 ms |
82744 KB |
Output is correct |
24 |
Correct |
98 ms |
77440 KB |
Output is correct |
25 |
Correct |
520 ms |
105216 KB |
Output is correct |
26 |
Correct |
429 ms |
99320 KB |
Output is correct |
27 |
Correct |
260 ms |
95716 KB |
Output is correct |
28 |
Correct |
292 ms |
89468 KB |
Output is correct |
29 |
Correct |
301 ms |
89524 KB |
Output is correct |
30 |
Correct |
168 ms |
86104 KB |
Output is correct |
31 |
Correct |
117 ms |
81708 KB |
Output is correct |
32 |
Correct |
136 ms |
79452 KB |
Output is correct |
33 |
Correct |
143 ms |
81976 KB |
Output is correct |
34 |
Correct |
295 ms |
88728 KB |
Output is correct |
35 |
Correct |
239 ms |
85468 KB |
Output is correct |
36 |
Correct |
305 ms |
91476 KB |
Output is correct |
37 |
Correct |
266 ms |
91320 KB |
Output is correct |
38 |
Correct |
275 ms |
95692 KB |
Output is correct |
39 |
Correct |
131 ms |
83140 KB |
Output is correct |
40 |
Correct |
304 ms |
89560 KB |
Output is correct |
41 |
Correct |
335 ms |
89576 KB |
Output is correct |
42 |
Correct |
239 ms |
92104 KB |
Output is correct |
43 |
Correct |
135 ms |
81804 KB |
Output is correct |
44 |
Correct |
238 ms |
87600 KB |
Output is correct |
45 |
Correct |
237 ms |
86476 KB |
Output is correct |
46 |
Correct |
194 ms |
86876 KB |
Output is correct |
47 |
Correct |
295 ms |
89924 KB |
Output is correct |
48 |
Correct |
616 ms |
111240 KB |
Output is correct |