oj.uz

답안 #923509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923509 2024-02-07T11:04:59 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 3932 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+5;
#else
    const int lim=3e3+3;
#endif

#include "bits/stdc++.h"
using namespace std;

#define int int64_t
#define pb push_back

const int mod=1e9+7;
//const int mod=(1ll<<61)-1;
using pii=pair<int,int>;

struct edge{
    int x,y,c,d;
};

template <>
struct std::hash<pii>{
  size_t operator()(const pii& k) const{
    return hash<int>()(k.first^(k.second<<10));
  }
};

const int inf=LLONG_MAX/10;
inline void solve(){
    int n,m;
    cin>>n>>m;
    edge all[m];
    for(int i=0;i<m;i++){
        cin>>all[i].x>>all[i].y>>all[i].c>>all[i].d;
        all[i].x--,all[i].y--;
    }
    int dist[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=inf;
        }
    }
    for(int i=0;i<m;i++){
        dist[all[i].x][all[i].y]=min(
            all[i].c,
            dist[all[i].x][all[i].y]
        );
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dist[i][j]=min(
                    dist[i][j],
                    dist[i][k]+dist[k][j]
                );
            }
        }
    }
    unordered_set<pii>v[n];
    for(int i=0;i<m;i++){
        v[all[i].x].insert(pii(all[i].y,all[i].c));
    }
    int ans=dist[0][n-1]+dist[n-1][0];
    //cerr<<ans<<"\n";
    for(auto[x,y,c,d]:all){
        //cerr<<x<<" "<<y<<" "<<c<<" "<<dist[y][x]<<"\n";
        if(dist[y][x]<=c)continue; // better upperbound exists
        v[x].erase({y,c});
        v[y].insert({x,c});
        int curd[n];
        for(int i=0;i<n;i++){
            curd[i]=inf;
        }
        curd[0]=0;
        bool vis[n];
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n-1;i++){
            int mini=-1;
            for(int j=0;j<n;j++){
                if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
                    mini=j;
                }
            }
            vis[mini]=1;
            if(mini==n-1)break;
            for(pii ed:v[mini]){
                curd[ed.first]=min(
                    curd[ed.first],
                    curd[mini]+ed.second
                );
            }
        }
        if(curd[n-1]==inf){
            v[y].erase({x,c});
            v[x].insert({y,c});
            continue;
        }
        //for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        //cerr<<"\n";
        int ansnow=curd[n-1];
        for(int i=0;i<n;i++){
            curd[i]=inf;
        }
        curd[n-1]=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n-1;i++){
            int mini=-1;
            for(int j=0;j<n;j++){
                if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
                    mini=j;
                }
            }
            vis[mini]=1;
            if(!mini)break;
            for(pii ed:v[mini]){
                curd[ed.first]=min(
                    curd[ed.first],
                    curd[mini]+ed.second
                );
            }
        }
        //for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        //cerr<<"\n";
        if(curd[0]!=inf){
            ansnow+=curd[0]+d;
            ans=min(ans,ansnow);
        }
        //cerr<<ansnow<<"\n\n";
        v[y].erase({x,c});
        v[x].insert({y,c});
    }
    if(ans<inf-100)cout<<ans<<"\n";
    else cout<<"-1\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else

#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 860 KB Output is correct
2 Correct 18 ms 604 KB Output is correct
3 Correct 83 ms 856 KB Output is correct
4 Correct 97 ms 856 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 20 ms 816 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 32 ms 860 KB Output is correct
11 Correct 36 ms 860 KB Output is correct
12 Correct 34 ms 860 KB Output is correct
13 Correct 76 ms 860 KB Output is correct
14 Correct 79 ms 856 KB Output is correct
15 Correct 61 ms 860 KB Output is correct
16 Correct 88 ms 860 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 849 ms 3816 KB Output is correct
2 Execution timed out 1032 ms 3812 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 860 KB Output is correct
2 Correct 16 ms 856 KB Output is correct
3 Correct 17 ms 3436 KB Output is correct
4 Correct 18 ms 604 KB Output is correct
5 Correct 21 ms 3932 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1056 ms 3768 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 860 KB Output is correct
2 Correct 18 ms 604 KB Output is correct
3 Correct 83 ms 856 KB Output is correct
4 Correct 97 ms 856 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 20 ms 816 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 32 ms 860 KB Output is correct
11 Correct 36 ms 860 KB Output is correct
12 Correct 34 ms 860 KB Output is correct
13 Correct 76 ms 860 KB Output is correct
14 Correct 79 ms 856 KB Output is correct
15 Correct 61 ms 860 KB Output is correct
16 Correct 88 ms 860 KB Output is correct
17 Correct 849 ms 3816 KB Output is correct
18 Execution timed out 1032 ms 3812 KB Time limit exceeded
19 Halted 0 ms 0 KB -