#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define mk make_pair
const int MAXN = 1e5+10 ;
const int MAXM = 2e5+10 ;
const ll inf = 1e18+10LL ;
using namespace std ;
int N , M ;
int cor[MAXM*2] ;
int j[MAXM*2] ;
ll p[MAXM*2] ;
map< pair<int, int> , ll > custo ;
map< pair<int,int> , int > chave ;
vector<int> adj[MAXN] ;
vector<pair<int,ll> > graph[MAXM*3] ;
void add(pair<int,int> par , ll val ){
if(custo.find(par) == custo.end()) custo[par] = 0 ;
custo[par] += val ;
}
int main()
{
ios_base::sync_with_stdio(false) ;
cin.tie(0) ;
cin >> N >> M ;
for(int i = 0 , a , b ; i < 2*M ; i += 2 ){
cin >> a >> b >> cor[i] >> p[i] ;
j[i] = b ;
j[i+1] = a ;
cor[i+1] = cor[i] ;
p[i+1] = p[i] ;
add( mk(a,cor[i]) , p[i] ) ;
add( mk(b,cor[i]) , p[i] ) ;
chave[mk(a,cor[i])] = chave[mk(b,cor[i])] = 0 ;
adj[a].push_back(i) ;
adj[b].push_back(i+1) ;
}
for(int i = 1 ; i <= N ; i++ ) chave[mk(i,0)] = 0 ;
int Key = 0 ;
for(auto &e : chave ) e.second = ++Key ;
for(int i = 1 ; i <= N ; i++ ){
int x = chave[mk(i,0)] ;
for(auto e : adj[i] ){
int y = chave[mk(i,cor[e])] ;
int a = chave[mk(j[e],0)] ;
int b = chave[mk(j[e],cor[e])] ;
graph[a].push_back( make_pair( y , custo[mk(i,cor[e])] - p[e] ) ) ;
graph[b].push_back( make_pair( x, 0 ) ) ;
graph[a].push_back( make_pair( x, p[e] ) ) ;
}
}
for(auto e : chave )
if(e.first.second) graph[ e.second ].push_back( mk( chave[mk(e.first.first,0)], 0 ) ) ;
vector<ll> dist(Key+1, inf ) ;
int T = chave[ mk(N,0) ] ;
priority_queue<pair<ll,int> , vector<pair<ll,int> > , greater<pair<ll,int> > > fila ;
fila.push( mk( dist[T] = 0 , T ) ) ;
while(!fila.empty()){
int x = fila.top().second ;
ll d = fila.top().first ;
fila.pop() ;
if(d != dist[x]) continue ;
for(auto e : graph[x]){
ll newD = d + e.second ;
int viz = e.first ;
if(newD >= dist[viz]) continue ;
fila.push( make_pair(dist[viz] = newD , viz) ) ;
}
}
int S = chave[ mk(1,0) ] ;
if(dist[S] == inf ) dist[S] = -1 ;
cout << dist[S] << "\n" ;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16716 KB |
Output is correct |
2 |
Correct |
9 ms |
16716 KB |
Output is correct |
3 |
Correct |
9 ms |
16772 KB |
Output is correct |
4 |
Correct |
9 ms |
16716 KB |
Output is correct |
5 |
Correct |
9 ms |
16744 KB |
Output is correct |
6 |
Correct |
9 ms |
16716 KB |
Output is correct |
7 |
Correct |
11 ms |
16972 KB |
Output is correct |
8 |
Correct |
10 ms |
16832 KB |
Output is correct |
9 |
Correct |
15 ms |
17612 KB |
Output is correct |
10 |
Correct |
14 ms |
17652 KB |
Output is correct |
11 |
Correct |
13 ms |
17356 KB |
Output is correct |
12 |
Correct |
14 ms |
17284 KB |
Output is correct |
13 |
Correct |
11 ms |
17424 KB |
Output is correct |
14 |
Correct |
12 ms |
17356 KB |
Output is correct |
15 |
Correct |
11 ms |
17228 KB |
Output is correct |
16 |
Correct |
14 ms |
17352 KB |
Output is correct |
17 |
Correct |
13 ms |
17228 KB |
Output is correct |
18 |
Correct |
11 ms |
17040 KB |
Output is correct |
19 |
Correct |
12 ms |
17356 KB |
Output is correct |
20 |
Correct |
13 ms |
17228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
424 ms |
45340 KB |
Output is correct |
2 |
Correct |
155 ms |
30916 KB |
Output is correct |
3 |
Correct |
483 ms |
50924 KB |
Output is correct |
4 |
Correct |
245 ms |
36584 KB |
Output is correct |
5 |
Correct |
1512 ms |
105516 KB |
Output is correct |
6 |
Correct |
1288 ms |
98212 KB |
Output is correct |
7 |
Correct |
733 ms |
84620 KB |
Output is correct |
8 |
Correct |
1153 ms |
83200 KB |
Output is correct |
9 |
Correct |
1156 ms |
83068 KB |
Output is correct |
10 |
Correct |
783 ms |
66380 KB |
Output is correct |
11 |
Correct |
514 ms |
55360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16716 KB |
Output is correct |
2 |
Correct |
9 ms |
16716 KB |
Output is correct |
3 |
Correct |
9 ms |
16772 KB |
Output is correct |
4 |
Correct |
9 ms |
16716 KB |
Output is correct |
5 |
Correct |
9 ms |
16744 KB |
Output is correct |
6 |
Correct |
9 ms |
16716 KB |
Output is correct |
7 |
Correct |
11 ms |
16972 KB |
Output is correct |
8 |
Correct |
10 ms |
16832 KB |
Output is correct |
9 |
Correct |
15 ms |
17612 KB |
Output is correct |
10 |
Correct |
14 ms |
17652 KB |
Output is correct |
11 |
Correct |
13 ms |
17356 KB |
Output is correct |
12 |
Correct |
14 ms |
17284 KB |
Output is correct |
13 |
Correct |
11 ms |
17424 KB |
Output is correct |
14 |
Correct |
12 ms |
17356 KB |
Output is correct |
15 |
Correct |
11 ms |
17228 KB |
Output is correct |
16 |
Correct |
14 ms |
17352 KB |
Output is correct |
17 |
Correct |
13 ms |
17228 KB |
Output is correct |
18 |
Correct |
11 ms |
17040 KB |
Output is correct |
19 |
Correct |
12 ms |
17356 KB |
Output is correct |
20 |
Correct |
13 ms |
17228 KB |
Output is correct |
21 |
Correct |
424 ms |
45340 KB |
Output is correct |
22 |
Correct |
155 ms |
30916 KB |
Output is correct |
23 |
Correct |
483 ms |
50924 KB |
Output is correct |
24 |
Correct |
245 ms |
36584 KB |
Output is correct |
25 |
Correct |
1512 ms |
105516 KB |
Output is correct |
26 |
Correct |
1288 ms |
98212 KB |
Output is correct |
27 |
Correct |
733 ms |
84620 KB |
Output is correct |
28 |
Correct |
1153 ms |
83200 KB |
Output is correct |
29 |
Correct |
1156 ms |
83068 KB |
Output is correct |
30 |
Correct |
783 ms |
66380 KB |
Output is correct |
31 |
Correct |
514 ms |
55360 KB |
Output is correct |
32 |
Correct |
349 ms |
50240 KB |
Output is correct |
33 |
Correct |
371 ms |
48264 KB |
Output is correct |
34 |
Correct |
879 ms |
71980 KB |
Output is correct |
35 |
Correct |
661 ms |
59276 KB |
Output is correct |
36 |
Correct |
774 ms |
70864 KB |
Output is correct |
37 |
Correct |
756 ms |
76584 KB |
Output is correct |
38 |
Correct |
737 ms |
86508 KB |
Output is correct |
39 |
Correct |
429 ms |
59776 KB |
Output is correct |
40 |
Correct |
1239 ms |
84588 KB |
Output is correct |
41 |
Correct |
1177 ms |
84548 KB |
Output is correct |
42 |
Correct |
1180 ms |
88304 KB |
Output is correct |
43 |
Correct |
535 ms |
52592 KB |
Output is correct |
44 |
Correct |
901 ms |
75624 KB |
Output is correct |
45 |
Correct |
942 ms |
72900 KB |
Output is correct |
46 |
Correct |
825 ms |
69048 KB |
Output is correct |
47 |
Correct |
751 ms |
74464 KB |
Output is correct |
48 |
Correct |
1616 ms |
113108 KB |
Output is correct |