#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=start-(start>end);x!=end-(start>end);x+=(start<end?1:-1))
#define all(x) x.begin(),x.end()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a, Args... args) { return max(a,MAX(args...)); }
template<typename... Args>
ll MIN(ll a, Args... args) { return min(a,MIN(args...)); }
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
const ll INF=1e18;
struct E{
int u,v;
ll len,flip;
int id;
E(int a,int b,int c,int d,int e){
u=a,v=b;
len=c,flip=d;
id=e;
}
};
int n,m;
vector<E> al[205];
vector<E> al_rev[205]; //store reversed edges
vector<E> edges;
priority_queue<ii,vector<ii>,greater<ii> > pq;
ll sf[205]; //source front
ll sb[205]; //source back
ll tf[205]; //sink front
ll tb[205]; //sink back
ll w[205];
map<int,ll> sp_f,sp_b; //is some edge in SP
ll temp,node; //stuff for dijk
void initial_d(){ //epic name
rep(x,0,205) sf[x]=sb[x]=tf[x]=tb[x]=INF;
sf[1]=0;
pq.push(ii(sf[1],1));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>sf[node]) continue; //important
for (auto &it:al[node]){
if (sf[it.v]>sf[node]+it.len){
sf[it.v]=sf[node]+it.len;
pq.push(ii (sf[it.v],it.v));
}
}
}
sb[1]=0;
pq.push(ii(sb[1],1));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>sb[node]) continue; //important
for (auto &it:al_rev[node]){
if (sb[it.v]>sb[node]+it.len){
sb[it.v]=sb[node]+it.len;
pq.push(ii (sb[it.v],it.v));
}
}
}
tf[n]=0;
pq.push(ii(tf[n],n));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>tf[node]) continue; //important
for (auto &it:al[node]){
if (tf[it.v]>tf[node]+it.len){
tf[it.v]=tf[node]+it.len;
pq.push(ii (tf[it.v],it.v));
}
}
}
tb[n]=0;
pq.push(ii(tb[n],n));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>tb[node]) continue; //important
for (auto &it:al_rev[node]){
if (tb[it.v]>tb[node]+it.len){
tb[it.v]=tb[node]+it.len;
pq.push(ii (tb[it.v],it.v));
}
}
}
}
void SP_d(){
if (sf[n]!=INF){ //find best from S to T
int curr=n;
while (curr!=1){
for (auto &it:al_rev[curr]){
if (sf[it.v]==sf[curr]-it.len){
curr=it.v;
sp_f[it.id]=0;;
break;
}
}
}
for (auto &it2:sp_f){
//we run a new iteration of dijkstra for this where we flip every edge on the SP
//cout<<edges[bad].u<<" "<<edges[bad].v<<endl;
rep(x,0,205) w[x]=INF;
w[1]=0;
pq.push(ii(w[1],1));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>w[node]) continue; //important
for (auto &it:al[node]){
if (it.id==edges[it2.first].id) continue;
if (w[it.v]>w[node]+it.len){
w[it.v]=w[node]+it.len;
pq.push(ii (w[it.v],it.v));
}
}
}
it2.second=w[n];
}
}
//find the path on best line from T->S
if (tf[1]!=INF){
int curr=1;
while (curr!=n){
for (auto &it:al_rev[curr]){
if (tf[it.v]==tf[curr]-it.len){
curr=it.v;
sp_b[it.id]=0;
break;
}
}
}
for (auto &it2:sp_b) {
//we run a new iteration of dijkstra for this where we flip every edge on the SP
//cout<<edges[bad].u<<" "<<edges[bad].v<<endl;
rep(x,0,205) w[x]=INF;
w[n]=0;
pq.push(ii(w[n],n));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>w[node]) continue; //important
for (auto &it:al[node]){
if (it.id==edges[it2.first].id) continue;
if (w[it.v]>w[node]+it.len){
w[it.v]=w[node]+it.len;
pq.push(ii (w[it.v],it.v));
}
}
}
it2.second=w[1];
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
int a,b,c,d;
rep(x,0,m){
cin>>a>>b>>c>>d;
al[a].push_back(E(a,b,c,d,x));
al_rev[b].push_back(E(b,a,c,d,x));
edges.push_back(E(a,b,c,d,x));
}
initial_d();
/*
rep(x,1,n+1){
cout<<sf[x]<<" "<<sb[x]<<" "<<tf[x]<<" "<<tb[x]<<endl;
}
*/
SP_d();
//try dijk start and end
ll ans=sf[n]+tf[1];
for (auto &it:edges){
ans=min(ans,min((sp_f.count(it.id)?sp_f[it.id]:sf[n]),sf[it.v]+tb[it.u]+it.len)+min((sp_b.count(it.id)?sp_b[it.id]:tf[1]),tf[it.v]+sb[it.u]+it.len)+it.flip);
}
if (ans>=INF) cout<<-1<<endl;
else cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
7912 KB |
Output is correct |
| 2 |
Correct |
33 ms |
7784 KB |
Output is correct |
| 3 |
Correct |
35 ms |
7920 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
6 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
34 ms |
8044 KB |
Output is correct |
| 10 |
Correct |
32 ms |
8048 KB |
Output is correct |
| 11 |
Correct |
36 ms |
7784 KB |
Output is correct |
| 12 |
Correct |
35 ms |
7912 KB |
Output is correct |
| 13 |
Correct |
37 ms |
7792 KB |
Output is correct |
| 14 |
Correct |
36 ms |
8552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
