제출 #364292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364292		farhan132	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	270 ms	9104 KiB

ho_t4

/***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;
      |        ^~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63