#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());
}
}
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];
// mpsm[clr[id]]=0;
mpf[clr[id]]=0;
}
for(int i=0;i<e[nw].size();i++){
int id=e[nw][i];
// mpsm[clr[id]]+=wr[id];
mpf[clr[id]]++;
}
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]+w){
dis[v]=dis[nw]+w;
pq.push({dis[v],v});
}
if(w&&mpe[v][clr[id]].size()>=2){
if(id!=mpe[v][clr[id]].back().second){
int neid=mpe[v][clr[id]].back().second;
w=mpsm[v][clr[id]]-wr[id]-wr[neid];
int vv=v^ar[neid]^br[neid];
if(dis[vv]>dis[v]+w){
dis[vv]=dis[v]+w;
pq.push({dis[vv],v});
}
}else{
int neid=mpe[v][clr[id]][mpe[v][clr[id]].size()-2].second;
w=mpsm[v][clr[id]]-wr[id]-wr[neid];
int vv=v^ar[neid]^br[neid];
if(dis[vv]>dis[v]+w){
dis[vv]=dis[v]+w;
pq.push({dis[vv],v});
}
}
}
}
}
int ans=dis[n];
if(dis[n]>=1e16){
ans=-1;
}
cout<<ans<<endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:44: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]
44 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:49: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]
49 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:54: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]
54 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
22 ms |
47240 KB |
Output is correct |
3 |
Correct |
23 ms |
47236 KB |
Output is correct |
4 |
Correct |
22 ms |
47316 KB |
Output is correct |
5 |
Correct |
23 ms |
47316 KB |
Output is correct |
6 |
Correct |
23 ms |
47316 KB |
Output is correct |
7 |
Incorrect |
27 ms |
47464 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
287 ms |
66788 KB |
Output is correct |
2 |
Incorrect |
119 ms |
56948 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
22 ms |
47240 KB |
Output is correct |
3 |
Correct |
23 ms |
47236 KB |
Output is correct |
4 |
Correct |
22 ms |
47316 KB |
Output is correct |
5 |
Correct |
23 ms |
47316 KB |
Output is correct |
6 |
Correct |
23 ms |
47316 KB |
Output is correct |
7 |
Incorrect |
27 ms |
47464 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |