#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define emp emplace
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 210;
const ll MAXE = 50100;
const ll INF = 1e15;
const ll MOD = 1e9+7;
typedef pair<pi,pi> pp;
typedef pair<ll,pi> pip;
vector<vector<pip>> V,O,S;
vi f1,fn,b1,bn;
ll N,E,a,b,w,r;
ll U[MAXE];
ll l[MAXN];
vector<pp> Edge;
priority_queue<pi,vpi,greater<pi>>pq;
ll BLOCK=-1;
void dijkstra(ll x, vector<vector<pip>> &A, vi &D){
// cout<<x<<'\n';
D.resize(N+1);
for(ll i=1;i<=N;++i)D[i]=INF;
D[x]=0;
pq.emp(0,x);
while(SZ(pq)){
pi t=pq.top();pq.pop();
ll n=t.s;ll d=t.f;
if(D[n]>d)continue;
if(n!=x)U[l[n]]=1;
for(auto t:A[n]){
ll c=t.f;ll nd=d+t.s.f;
if(nd>=D[c])continue;
if(t.s.s==BLOCK)continue;
D[c]=nd;
l[c]=t.s.s;
pq.emp(nd,c);
}
}
}
int main(){
cin>>N>>E;
V.resize(N+1);O.resize(N+1);S.resize(N+1);
for (ll i=0;i<E;++i){
cin>>a>>b>>w>>r;
V[a].pb(b, mp(w,i));
O[b].pb(a, mp(w,i));
Edge.pb(mp(a,b),mp(w,r));
}
dijkstra(1,V,f1);
dijkstra(N,V,fn);
dijkstra(1,O,b1);
dijkstra(N,O,bn);
// for (ll i=0;i<E;++i)cout<<U[i]<<' ';cout<<'\n';
ll ans=f1[N]+bn[1];
// cout<<ans<<'\n';
for(ll i=0;i<E;++i)if(U[i]){
S[Edge[i].f.f].pb(Edge[i].f.s, mp(Edge[i].s.f, i));
}
for(ll i=0;i<E;++i)if(!U[i]){
ll a=Edge[i].f.f;ll b=Edge[i].f.s;ll w=Edge[i].s.f;
ll forward=min(f1[N],f1[b]+w+bn[a]);
ll back=min(fn[1],fn[b]+w+b1[a]);
ll tw=Edge[i].s.s+forward+back;
ans=min(ans,tw);
}
for (ll i=0;i<E;++i)if(U[i]){
ll a=Edge[i].f.f;ll b=Edge[i].f.s;ll w=Edge[i].s.f;
BLOCK=i;
vi d1,d2;
V[b].pb(a,mp(w,0));
dijkstra(1,V,d1);dijkstra(N,V,d2);
ll tw=Edge[i].s.s+d1[N]+d2[1];
// cout<<tw<<'\n';
ans=min(ans,tw);
V[b].pop_back();
}
if(ans>=INF)cout<<-1;
else cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Incorrect |
38 ms |
512 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
733 ms |
6244 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
194 ms |
4968 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
239 ms |
5860 KB |
Output is correct |
6 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Incorrect |
38 ms |
512 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |