#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popf pop_frot
#define popb pop_back
#define int long long
#define in insert
#define mid (l+r)/2
//register int cnt
using namespace std;
const int N=1e5+5;
int n,m,tree[N*8],d[N],vis[N];
vector<pair<int,int>> adj[N];
vector<pair<int,pair<int,int>>> E[N];
void upd(int node , int l , int r , int id , int v){
if(l==r){
tree[node]+=v;
return ;
}
else if(id<=mid) upd(node*2,l,mid,id,v);
else upd(node*2+1,mid+1,r,id,v);
tree[node]=min(tree[node*2],tree[node*2+1]);
return ;
}
int query(int node , int l , int r , int s , int e){
if(l>=s && r<=e) return tree[node];
else if(l>e || r<s) return 1e17;
return min(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e));
}
void dfs(int node){
vis[node]=1;
if(E[node].size()>1) return ;
for(auto u : E[node]){
if(vis[u.F]) continue ;
dfs(u.F);
}
return ;
}
void Dijkstra(){
for(int i=1;i<=n;i++) d[i]=1e18;
d[1]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({0,1});
while(!q.empty()){
int node=q.top().S,D=q.top().F;
q.pop();
if(vis[node]) continue ;
vis[node]=1;
for(auto u : adj[node]){
if(d[u.F]>D+u.S){
d[u.F]=D+u.S;
q.push({d[u.F],u.F});
}
}
}
return;
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,c,p;
cin>>u>>v>>c>>p;
E[u].pb({v,{c,p}});
E[v].pb({u,{c,p}});
}
for(int i=1;i<=n;i++){
for(auto u : E[i]){
upd(1,1,m,u.S.F,u.S.S);
}
for(auto u : E[i]){
adj[i].pb({u.F,min(u.S.S+tree[1],query(1,1,m,u.S.F,u.S.F)-u.S.S)});
}
for(auto u : E[i]){
upd(1,1,m,u.S.F,-u.S.S);
}
}
if(m==1){
dfs(1);
if(vis[n]) cout<<0;
else cout<<-1;
}
else{
Dijkstra();
if(d[n]==1e18) cout<<-1;
else cout<<d[n];
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |