#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 w1[205];
ll w2[205];
bool path[50005]; //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));
}
}
}
}
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;
}
*/
//try dijk start and end
ll ans=sf[n]+tf[1];
//find the path on best line from S->T
if (sf[n]!=INF){
memset(path,false,sizeof(path));
int curr=n;
while (curr!=1){
for (auto &it:al_rev[curr]){
if (sf[it.v]==sf[curr]-it.len){
curr=it.v;
path[it.id]=true;
break;
}
}
}
for (auto &it:edges){
if (path[it.id]) continue;
ans=min(ans,sf[n]+tf[it.v]+sb[it.u]+it.len+it.flip);
}
rep(bad,0,m) if (path[bad]) {
//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;
al[edges[bad].v].push_back(E(-1,edges[bad].u,edges[bad].len,-1,-1));
rep(x,0,205) w1[x]=w2[x]=INF;
w1[1]=0;
pq.push(ii(w1[1],1));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>w1[node]) continue; //important
for (auto &it:al[node]){
if (it.id==edges[bad].id) continue;
if (w1[it.v]>w1[node]+it.len){
w1[it.v]=w1[node]+it.len;
pq.push(ii (w1[it.v],it.v));
}
}
}
w2[n]=0;
pq.push(ii(w2[n],n));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>w2[node]) continue; //important
for (auto &it:al[node]){
if (it.id==edges[bad].id) continue;
if (w2[it.v]>w2[node]+it.len){
w2[it.v]=w2[node]+it.len;
pq.push(ii (w2[it.v],it.v));
}
}
}
ans=min(ans,w1[n]+w2[1]+edges[bad].flip);
al[edges[bad].v].pop_back();
}
}
//find the path on best line from T->S
if (tf[1]!=INF){
memset(path,false,sizeof(path));
int curr=1;
while (curr!=n){
for (auto &it:al_rev[curr]){
if (tf[it.v]==tf[curr]-it.len){
curr=it.v;
path[it.id]=true;
break;
}
}
}
for (auto &it:edges){
if (path[it.id]) continue;
ans=min(ans,tf[1]+sf[it.v]+tb[it.u]+it.len+it.flip);
}
rep(bad,0,m) if (path[bad]) {
//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;
al[edges[bad].v].push_back(E(-1,edges[bad].u,edges[bad].len,-1,-1));
rep(x,0,205) w1[x]=w2[x]=INF;
w1[1]=0;
pq.push(ii(w1[1],1));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>w1[node]) continue; //important
for (auto &it:al[node]){
if (it.id==edges[bad].id) continue;
if (w1[it.v]>w1[node]+it.len){
w1[it.v]=w1[node]+it.len;
pq.push(ii (w1[it.v],it.v));
}
}
}
w2[n]=0;
pq.push(ii(w2[n],n));
while (!pq.empty()){
temp=pq.top().first;
node=pq.top().second;
pq.pop();
if (temp>w2[node]) continue; //important
for (auto &it:al[node]){
if (it.id==edges[bad].id) continue;
if (w2[it.v]>w2[node]+it.len){
w2[it.v]=w2[node]+it.len;
pq.push(ii (w2[it.v],it.v));
}
}
}
ans=min(ans,w1[n]+w2[1]+edges[bad].flip);
al[edges[bad].v].push_back(E(-1,edges[bad].u,edges[bad].len,-1,-1));
}
}
if (ans>=INF) cout<<-1<<endl;
else cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
7016 KB |
Output is correct |
| 2 |
Correct |
35 ms |
7012 KB |
Output is correct |
| 3 |
Correct |
36 ms |
6768 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 |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Incorrect |
29 ms |
6768 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
