#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];
vector<int>dis[200005];
vector<int>vis[200005];
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
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);
dis[ar[i]].push_back(1e18);
vis[ar[i]].push_back(0);
dis[br[i]].push_back(1e18);
vis[br[i]].push_back(0);
}
for(int i=1;i<=n;i++){
dis[i].push_back(1e18);
vis[i].push_back(0);
}
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>> >,greater<pair<int,pair<int,int>>>>pq;
pq.push({0,{1,e[1].size()}});
dis[1][e[1].size()]=0;
while(pq.size()){
int nw=pq.top().second.first;
int nwc=pq.top().second.second;
pq.pop();
if(vis[nw][nwc]){continue;}
vis[nw][nwc]=1;
// cout<<nw<<" "<<nwc<<endl;
map<int,int>mpsm;
for(int i=0;i<e[nw].size();i++){
if(i==nwc){continue;}
int id=e[nw][i];
mpsm[clr[id]]+=wr[id];
}
for(int i=0;i<e[nw].size();i++){
int id=e[nw][i];
if(i==nwc){continue;}
int v=ar[id]^br[id]^nw;
int w=wr[id];
int eid=lower_bound(e[v].begin(),e[v].end(),id)-e[v].begin();
if(dis[v][eid]>dis[nw][nwc]+w){
dis[v][eid]=dis[nw][nwc]+w;
pq.push({dis[v][eid],{v,eid}});
}
w=mpsm[clr[id]]-wr[id];
eid=e[v].size();
if(dis[v][eid]>dis[nw][nwc]+w){
dis[v][eid]=dis[nw][nwc]+w;
pq.push({dis[v][eid],{v,eid}});
}
// cout<<"hihi\n";
}
}
int ans=dis[n][0];
for(int i=0;i<=e[n].size();i++){
ans=min(ans,dis[n][i]);
}
if(ans>=1e18){
ans=-1;
}
cout<<ans<<endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:42: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]
42 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:47: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]
47 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:68:14: 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]
68 | for(int i=0;i<=e[n].size();i++){
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14364 KB |
Output is correct |
2 |
Correct |
10 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14372 KB |
Output is correct |
6 |
Correct |
8 ms |
14336 KB |
Output is correct |
7 |
Correct |
13 ms |
14548 KB |
Output is correct |
8 |
Correct |
10 ms |
14420 KB |
Output is correct |
9 |
Correct |
251 ms |
14884 KB |
Output is correct |
10 |
Correct |
167 ms |
14944 KB |
Output is correct |
11 |
Correct |
71 ms |
14876 KB |
Output is correct |
12 |
Correct |
31 ms |
14848 KB |
Output is correct |
13 |
Correct |
53 ms |
14896 KB |
Output is correct |
14 |
Correct |
66 ms |
14892 KB |
Output is correct |
15 |
Correct |
10 ms |
14548 KB |
Output is correct |
16 |
Correct |
12 ms |
14668 KB |
Output is correct |
17 |
Correct |
11 ms |
14656 KB |
Output is correct |
18 |
Correct |
9 ms |
14464 KB |
Output is correct |
19 |
Correct |
20 ms |
14764 KB |
Output is correct |
20 |
Correct |
9 ms |
14548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
27484 KB |
Output is correct |
2 |
Correct |
165 ms |
20668 KB |
Output is correct |
3 |
Correct |
684 ms |
36160 KB |
Output is correct |
4 |
Correct |
168 ms |
24604 KB |
Output is correct |
5 |
Execution timed out |
3099 ms |
50076 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14364 KB |
Output is correct |
2 |
Correct |
10 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14372 KB |
Output is correct |
6 |
Correct |
8 ms |
14336 KB |
Output is correct |
7 |
Correct |
13 ms |
14548 KB |
Output is correct |
8 |
Correct |
10 ms |
14420 KB |
Output is correct |
9 |
Correct |
251 ms |
14884 KB |
Output is correct |
10 |
Correct |
167 ms |
14944 KB |
Output is correct |
11 |
Correct |
71 ms |
14876 KB |
Output is correct |
12 |
Correct |
31 ms |
14848 KB |
Output is correct |
13 |
Correct |
53 ms |
14896 KB |
Output is correct |
14 |
Correct |
66 ms |
14892 KB |
Output is correct |
15 |
Correct |
10 ms |
14548 KB |
Output is correct |
16 |
Correct |
12 ms |
14668 KB |
Output is correct |
17 |
Correct |
11 ms |
14656 KB |
Output is correct |
18 |
Correct |
9 ms |
14464 KB |
Output is correct |
19 |
Correct |
20 ms |
14764 KB |
Output is correct |
20 |
Correct |
9 ms |
14548 KB |
Output is correct |
21 |
Correct |
354 ms |
27484 KB |
Output is correct |
22 |
Correct |
165 ms |
20668 KB |
Output is correct |
23 |
Correct |
684 ms |
36160 KB |
Output is correct |
24 |
Correct |
168 ms |
24604 KB |
Output is correct |
25 |
Execution timed out |
3099 ms |
50076 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |