#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define tr(it,a) for(auto it:a)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define umin(x,y) (x=min(x,(y)))
#define umax(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
//
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define __db
#ifdef __db
#define IOS
#define prt(...) cerr<<__VA_ARGS__
#define ary(s,t) for(auto it=(s);it!=(t);++it)prt(*it<<" ");prt(endl);
#else
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
#define prt(...)
#define ary(...)
#endif
//
struct ed{
int u,v,c,d;
};
const int maxn=209,maxm=5e4+9,inf=1ll<<60;
int n,m,res=inf,pre[maxn],dis[2][2][maxn];
bitset<maxn>ok,used;
vector<int>g[maxn],rg[maxn];
ed eds[maxm];
int dijk(vector<int>*gg,int*dd,int s,int t,int rev){
fill(dd,dd+n,inf);
ok.reset();
dd[s]=0;
REP(k,0,n){
int u=-1;
REP(i,0,n){
if(!ok[i]&&(u<0||dd[i]<dd[u])){
u=i;
}
}
ok[u]=1;
if(rev>=0&&(u==eds[rev].u||u==eds[rev].v)){
int ex=0;
REP(i,0,gg[u].size())ex|=gg[u][i]==rev;
if(!ex){
int v=u^eds[rev].u^eds[rev].v;
if(dd[v]>dd[u]+eds[rev].c){
dd[v]=dd[u]+eds[rev].c;
pre[v]=rev;
}
}
}
REP(i,0,gg[u].size()){
int e=gg[u][i],v=u^eds[e].u^eds[e].v;
if(e!=rev&&dd[v]>dd[u]+eds[e].c){
dd[v]=dd[u]+eds[e].c;
pre[v]=e;
}
}
}
return dd[t];
}
main(){
IOS;
cin>>n>>m;
REP(i,0,m){
int u,v,c,d;cin>>u>>v>>c>>d,--u,--v;
eds[i]=ed{u,v,c,d};
g[u].pb(i);
rg[v].pb(i);
}
dijk(g,dis[0][0],0,n-1,-1);
REP(i,1,n)used[pre[i]]=1;
dijk(g,dis[0][1],n-1,0,-1);
REP(i,0,n-1)used[pre[i]]=1;
dijk(rg,dis[1][0],0,n-1,-1);
dijk(rg,dis[1][1],n-1,0,-1);
REP(i,0,m){
if(!used[i]){
int x=min(dis[0][0][n-1],dis[0][0][eds[i].v]+eds[i].c+dis[1][1][eds[i].u]);
int y=min(dis[0][1][0],dis[0][1][eds[i].v]+eds[i].c+dis[1][0][eds[i].u]);
umin(res,eds[i].d+x+y);
}
}
REP(i,0,m){
if(used[i]){
umin(res,eds[i].c+dijk(g,dis[0][0],0,n-1,i)+dijk(g,dis[0][0],n-1,0,i));
}
}
cout<<res<<endl;
}
Compilation message
ho_t4.cpp: In function 'int_fast64_t dijk(std::vector<long int>*, int_fast64_t*, int_fast64_t, int_fast64_t, int_fast64_t)':
ho_t4.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i,j,k) for(int i=(j);i<(k);++i)
^
ho_t4.cpp:63:4: note: in expansion of macro 'REP'
REP(i,0,gg[u].size())ex|=gg[u][i]==rev;
^~~
ho_t4.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i,j,k) for(int i=(j);i<(k);++i)
^
ho_t4.cpp:72:3: note: in expansion of macro 'REP'
REP(i,0,gg[u].size()){
^~~
ho_t4.cpp: At global scope:
ho_t4.cpp:83:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
4216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
