#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;int m;
int ar[200005];int br[200005];int clr[200005];int wr[200005];
vector<int>e[200005];
int dis[200005];
int vis[200005];
map<int,int>mpsm[500005];
int mpf[500005];
map<int,vector<pair<int,int>>>mpe[200005];
map<int,int>mxe[200005];
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>ar[i]>>br[i]>>clr[i]>>wr[i];
e[ar[i]].push_back(i);
e[br[i]].push_back(i);
mpe[ar[i]][clr[i]].push_back({wr[i],i});
mpe[br[i]][clr[i]].push_back({wr[i],i});
mpsm[ar[i]][clr[i]]+=wr[i];
mpsm[br[i]][clr[i]]+=wr[i];
}
for(int i=1;i<=n;i++){
dis[i]=1e18;
vis[i]=0;
for(auto it=mpsm[i].begin();it!=mpsm[i].end();it++){
sort(mpe[i][(*it).first].begin(),mpe[i][(*it).first].end());
reverse(mpe[i][(*it).first].begin(),mpe[i][(*it).first].end());
}
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
dis[1]=0;
pq.push({0,1});
while(pq.size()){
int nw=pq.top().second;
pq.pop();
if(vis[nw]){continue;}
vis[nw]=1;
for(int i=0;i<e[nw].size();i++){
int id=e[nw][i];
int v=ar[id]^br[id]^nw;
//if(vis[v]){continue;}
int w=wr[id];
// if(mpf[clr[id]]==1){
// w=0;
//}
if(dis[v]>dis[nw]+min(w,mpsm[nw][clr[id]]-w) ){
dis[v]=dis[nw]+min(w,mpsm[nw][clr[id]]-w);
pq.push({dis[v],v});
}
int ow=dis[nw]+w;int cnt=3;
for(int j=0;j<mpe[v][clr[id]].size();j++){
// cout<<nw<<" "<<id<<endl;
cnt--;
if(cnt<0){break;}
if(id!=mpe[v][clr[id]][j].second){
int neid=mpe[v][clr[id]][j].second;
int vv=v^ar[neid]^br[neid];
w=mpsm[v][clr[id]]-wr[id]-wr[neid];
// cout<<nw<<" "<<v<<" "<<vv<<" "<<neid<<" "<<ow<<" "<<w<<endl;
if(dis[vv]>ow+w){
dis[vv]=ow+w;
pq.push({dis[vv],vv});
}
}
}
}
}
int ans=dis[n];
if(dis[n]>=1e16){
ans=-1;
}
cout<<ans<<endl;
}
/*
6 5
1 2 1 100000
1 3 1 1
2 6 1 1000
2 4 1 1
2 5 1 1
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:45:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:58:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int j=0;j<mpe[v][clr[id]].size();j++){
| ~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47304 KB |
Output is correct |
2 |
Correct |
27 ms |
47316 KB |
Output is correct |
3 |
Correct |
27 ms |
47284 KB |
Output is correct |
4 |
Correct |
25 ms |
47200 KB |
Output is correct |
5 |
Correct |
22 ms |
47316 KB |
Output is correct |
6 |
Correct |
21 ms |
47264 KB |
Output is correct |
7 |
Correct |
23 ms |
47388 KB |
Output is correct |
8 |
Correct |
28 ms |
47316 KB |
Output is correct |
9 |
Correct |
33 ms |
47832 KB |
Output is correct |
10 |
Correct |
32 ms |
47856 KB |
Output is correct |
11 |
Correct |
22 ms |
47700 KB |
Output is correct |
12 |
Correct |
25 ms |
47576 KB |
Output is correct |
13 |
Correct |
23 ms |
47676 KB |
Output is correct |
14 |
Correct |
25 ms |
47688 KB |
Output is correct |
15 |
Correct |
24 ms |
47520 KB |
Output is correct |
16 |
Correct |
28 ms |
47620 KB |
Output is correct |
17 |
Correct |
29 ms |
47656 KB |
Output is correct |
18 |
Correct |
29 ms |
47444 KB |
Output is correct |
19 |
Correct |
27 ms |
47628 KB |
Output is correct |
20 |
Correct |
25 ms |
47564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
339 ms |
66764 KB |
Output is correct |
2 |
Correct |
117 ms |
56932 KB |
Output is correct |
3 |
Correct |
492 ms |
69072 KB |
Output is correct |
4 |
Correct |
217 ms |
60532 KB |
Output is correct |
5 |
Correct |
1381 ms |
107592 KB |
Output is correct |
6 |
Correct |
1189 ms |
99764 KB |
Output is correct |
7 |
Correct |
638 ms |
85844 KB |
Output is correct |
8 |
Correct |
667 ms |
86872 KB |
Output is correct |
9 |
Correct |
678 ms |
86876 KB |
Output is correct |
10 |
Correct |
487 ms |
80600 KB |
Output is correct |
11 |
Correct |
255 ms |
70468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47304 KB |
Output is correct |
2 |
Correct |
27 ms |
47316 KB |
Output is correct |
3 |
Correct |
27 ms |
47284 KB |
Output is correct |
4 |
Correct |
25 ms |
47200 KB |
Output is correct |
5 |
Correct |
22 ms |
47316 KB |
Output is correct |
6 |
Correct |
21 ms |
47264 KB |
Output is correct |
7 |
Correct |
23 ms |
47388 KB |
Output is correct |
8 |
Correct |
28 ms |
47316 KB |
Output is correct |
9 |
Correct |
33 ms |
47832 KB |
Output is correct |
10 |
Correct |
32 ms |
47856 KB |
Output is correct |
11 |
Correct |
22 ms |
47700 KB |
Output is correct |
12 |
Correct |
25 ms |
47576 KB |
Output is correct |
13 |
Correct |
23 ms |
47676 KB |
Output is correct |
14 |
Correct |
25 ms |
47688 KB |
Output is correct |
15 |
Correct |
24 ms |
47520 KB |
Output is correct |
16 |
Correct |
28 ms |
47620 KB |
Output is correct |
17 |
Correct |
29 ms |
47656 KB |
Output is correct |
18 |
Correct |
29 ms |
47444 KB |
Output is correct |
19 |
Correct |
27 ms |
47628 KB |
Output is correct |
20 |
Correct |
25 ms |
47564 KB |
Output is correct |
21 |
Correct |
339 ms |
66764 KB |
Output is correct |
22 |
Correct |
117 ms |
56932 KB |
Output is correct |
23 |
Correct |
492 ms |
69072 KB |
Output is correct |
24 |
Correct |
217 ms |
60532 KB |
Output is correct |
25 |
Correct |
1381 ms |
107592 KB |
Output is correct |
26 |
Correct |
1189 ms |
99764 KB |
Output is correct |
27 |
Correct |
638 ms |
85844 KB |
Output is correct |
28 |
Correct |
667 ms |
86872 KB |
Output is correct |
29 |
Correct |
678 ms |
86876 KB |
Output is correct |
30 |
Correct |
487 ms |
80600 KB |
Output is correct |
31 |
Correct |
255 ms |
70468 KB |
Output is correct |
32 |
Correct |
411 ms |
68788 KB |
Output is correct |
33 |
Correct |
383 ms |
67652 KB |
Output is correct |
34 |
Correct |
670 ms |
85512 KB |
Output is correct |
35 |
Correct |
538 ms |
77648 KB |
Output is correct |
36 |
Correct |
524 ms |
80752 KB |
Output is correct |
37 |
Correct |
573 ms |
87136 KB |
Output is correct |
38 |
Correct |
622 ms |
89540 KB |
Output is correct |
39 |
Correct |
456 ms |
74468 KB |
Output is correct |
40 |
Correct |
750 ms |
92228 KB |
Output is correct |
41 |
Correct |
854 ms |
92500 KB |
Output is correct |
42 |
Correct |
1000 ms |
98444 KB |
Output is correct |
43 |
Correct |
416 ms |
72628 KB |
Output is correct |
44 |
Correct |
1056 ms |
83892 KB |
Output is correct |
45 |
Correct |
589 ms |
84540 KB |
Output is correct |
46 |
Correct |
503 ms |
83888 KB |
Output is correct |
47 |
Correct |
567 ms |
84440 KB |
Output is correct |
48 |
Correct |
1386 ms |
113364 KB |
Output is correct |