제출 #364292

#제출 시각아이디문제언어결과실행 시간메모리
364292farhan132Olympic Bus (JOI20_ho_t4)C++17
100 / 100
270 ms9104 KiB
/***Farhan132***/ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double dd; typedef vector<ll> vll; typedef pair<ll , ll> ii; typedef vector< ii > vii; typedef pair < pair < ll , ll > , pair < ll , ll > > cm; #define ff first #define ss second #define pb push_back #define in insert #define f0(b) for(int i=0;i<(b);i++) #define f00(b) for(int j=0;j<(b);j++) #define f1(b) for(int i=1;i<=(b);i++) #define f11(b) for(int j=1;j<=(b);j++) #define f2(a,b) for(int i=(a);i<=(b);i++) #define f22(a,b) for(int j=(a);j<=(b);j++) #define sf(a) scanf("%lld",&a) #define sff(a,b) scanf("%lld %lld", &a , &b) #define pf(a) printf("%lld\n",a) #define pff(a,b) printf("%lld %lld\n", a , b) #define PI 3.14159265359 #define bug printf("**!\n") #define mem(a , b) memset(a, b ,sizeof(a)) #define front_zero(n) __builtin_clzll(n) #define back_zero(n) __builtin_ctzll(n) #define total_one(n) __builtin_popcountll(n) #define clean fflush(stdout) const ll mod = (ll)1e9 + 7; const ll maxn = (ll)2e5 + 5; const int nnn = 1048590; const int inf = numeric_limits<int>::max()-1; //const ll INF = numeric_limits<ll>::max()-1; //const ll INF = 1e18; ll dx[]={0,1,0,-1}; ll dy[]={1,0,-1,0}; ll dxx[]={0,1,0,-1,1,1,-1,-1}; ll dyy[]={1,0,-1,0,1,-1,1,-1}; struct edge{ ll x, y , cost, r , id; }; struct thing{ ll D , p , e; ll vis; }; ll n , m; vector < edge > g; vector < edge > v[205] , rev[205]; set < ll > cool; ll par[10][205]; ll f[10][205]; ll dis[10][205]; edge W; thing t[205]; void shortest(ll x, ll w, ll lol, edge kk){ if(lol != -1) for(ll i = 1; i <= n; i++) dis[w][i] = -1; for(ll i = 1; i <= n; i++){ t[i].D = 1e18; t[i].p = -1; t[i].e = -1; t[i].vis = 0; par[w][i] = -1; } t[x].D = 0; while(1){ thing final; final.D = 1e18; ll node = -1; for(ll i = 1; i <= n; i++){ if(t[i].vis) continue; if(t[i].D < final.D) final = t[i] , node = i; } if(node == -1) break; dis[w][node] = t[node].D; par[w][node] = t[node].p; f[w][node] = t[node].e; t[node].vis = 1; if(w <= 1){ for(edge u : v[node]){ if(!t[u.y].vis && t[u.y].D > dis[w][node] + u.cost ) t[u.y] = {dis[w][node] + u.cost , node , u.id , 0}; } }else if(w <= 3){ for(edge u : rev[node]){ if(!t[u.y].vis && t[u.y].D > dis[w][node] + u.cost ) t[u.y] = {dis[w][node] + u.cost , node , u.id , 0}; } }else if(w <= 5){ for(edge u : v[node]){ if(!t[u.y].vis && t[u.y].D > dis[w][node] + u.cost && u.id != lol) t[u.y] = {dis[w][node] + u.cost , node , u.id , 0}; } if(kk.x == node && !t[kk.y].vis && t[kk.y].D > dis[w][node] + kk.cost + kk.r) t[kk.y] = {dis[w][node] + kk.cost + kk.r, node , kk.id , 0}; } } if(w >= 2) return; ll cur = 1; if(x == 1) cur = n; if(dis[w][cur] == -1) return; ll cnt = 0; while(1){ if(par[w][cur] == -1) break; cool.in(f[w][cur]); cur = par[w][cur]; } return; } void solve(){ cin >> n >> m; for(ll i = 1; i <= m; i++){ ll x , y , cost , r; cin >> x >> y >> cost >> r; v[x].pb({x,y,cost,r,i}); rev[y].pb({y,x,cost,r,i}); g.pb({x,y,cost,r,i}); } mem(dis,-1); shortest(1, 0, -1, W); shortest(n, 1, -1, W); shortest(1, 2, -1, W); shortest(n, 3, -1, W); ll ans = 1e18; if(dis[0][n] != -1 && dis[1][1] != -1) ans = dis[1][1] + dis[0][n]; for(edge u : g){ if(cool.count(u.id)){ edge passing; passing = u; passing.y = u.x; passing.x = u.y; shortest(1, 4, u.id, passing); shortest(n, 5, u.id, passing); if(dis[4][n] == -1 || dis[5][1] == -1) continue; ans = min(ans , dis[4][n] + dis[5][1]); }else{ ll X = 1e18 , Y = 1e18; if(dis[0][n] != -1) X = dis[0][n]; if(dis[1][1] != -1) Y = dis[1][1]; if(dis[0][u.y] != -1 && dis[3][u.x] != -1) X = min(X , dis[0][u.y] + dis[3][u.x] + u.cost ); if(dis[1][u.y] != -1 && dis[2][u.x] != -1) Y = min(Y, dis[1][u.y] + dis[2][u.x] + u.cost ); ans = min(ans , X + Y + u.r); } } if(ans == 1e18) ans = -1; cout << ans; return; } int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #else // freopen("cbarn2.in", "r", stdin); // freopen("cbarn2.out", "w", stdout); // ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); #endif //cout << fixed << setprecision(10); // work(maxn); // mem(b,0); ll T; T=1; //cin >> T; //scanf("%lld",&T); // ll CT = 0; //work(); while(T--){ //cout << "Case " << ++CT <<": " ; //printf("Case %lld: ",++CT); solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'void shortest(ll, ll, ll, edge)':
ho_t4.cpp:111:8: warning: unused variable 'cnt' [-Wunused-variable]
  111 |     ll cnt = 0;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...