#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];
int mpsm[500005];
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]]=0;
}
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:43: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]
43 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:48: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]
48 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:53: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]
53 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:74: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]
74 | for(int i=0;i<=e[n].size();i++){
| ~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
10 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14408 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14524 KB |
Output is correct |
7 |
Correct |
9 ms |
14548 KB |
Output is correct |
8 |
Correct |
9 ms |
14544 KB |
Output is correct |
9 |
Correct |
44 ms |
14932 KB |
Output is correct |
10 |
Correct |
35 ms |
14804 KB |
Output is correct |
11 |
Correct |
58 ms |
14908 KB |
Output is correct |
12 |
Correct |
27 ms |
14804 KB |
Output is correct |
13 |
Correct |
59 ms |
14920 KB |
Output is correct |
14 |
Correct |
50 ms |
14932 KB |
Output is correct |
15 |
Correct |
9 ms |
14568 KB |
Output is correct |
16 |
Correct |
12 ms |
14724 KB |
Output is correct |
17 |
Correct |
10 ms |
14676 KB |
Output is correct |
18 |
Correct |
9 ms |
14548 KB |
Output is correct |
19 |
Correct |
15 ms |
14804 KB |
Output is correct |
20 |
Correct |
9 ms |
14676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
290 ms |
27472 KB |
Output is correct |
2 |
Correct |
91 ms |
20640 KB |
Output is correct |
3 |
Correct |
566 ms |
36240 KB |
Output is correct |
4 |
Correct |
144 ms |
24572 KB |
Output is correct |
5 |
Execution timed out |
3097 ms |
48608 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
10 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14408 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
8 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14524 KB |
Output is correct |
7 |
Correct |
9 ms |
14548 KB |
Output is correct |
8 |
Correct |
9 ms |
14544 KB |
Output is correct |
9 |
Correct |
44 ms |
14932 KB |
Output is correct |
10 |
Correct |
35 ms |
14804 KB |
Output is correct |
11 |
Correct |
58 ms |
14908 KB |
Output is correct |
12 |
Correct |
27 ms |
14804 KB |
Output is correct |
13 |
Correct |
59 ms |
14920 KB |
Output is correct |
14 |
Correct |
50 ms |
14932 KB |
Output is correct |
15 |
Correct |
9 ms |
14568 KB |
Output is correct |
16 |
Correct |
12 ms |
14724 KB |
Output is correct |
17 |
Correct |
10 ms |
14676 KB |
Output is correct |
18 |
Correct |
9 ms |
14548 KB |
Output is correct |
19 |
Correct |
15 ms |
14804 KB |
Output is correct |
20 |
Correct |
9 ms |
14676 KB |
Output is correct |
21 |
Correct |
290 ms |
27472 KB |
Output is correct |
22 |
Correct |
91 ms |
20640 KB |
Output is correct |
23 |
Correct |
566 ms |
36240 KB |
Output is correct |
24 |
Correct |
144 ms |
24572 KB |
Output is correct |
25 |
Execution timed out |
3097 ms |
48608 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |