oj.uz

답안 #923544

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923544 2024-02-07T12:06:12 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 7200 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{
        int first=hash<int>()(k.first),second=hash<int>()(k.second);
        return hash<int>()(first^second);
    }
};
const int inf=INT_MAX*200ll;
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]
                );
            }
        }
    }
    multiset<int>v[n][n];
    for(int i=0;i<m;i++){
        v[all[i].x][all[i].y].insert(all[i].c);
        if(2<v[all[i].x][all[i].y].size()){
            auto p=v[all[i].x][all[i].y].end();
            p--;
            v[all[i].x][all[i].y].erase(p);
        }
    }
    //cerr<<"ok\n";
    int ans=dist[0][n-1]+dist[n-1][0];
    //cerr<<ans<<"\n";
    for(auto[x,y,c,d]:all){
        //cerr<<"\n"<<x<<" "<<y<<" "<<c<<" "<<dist[y][x]<<"\n";
        if(dist[y][x]<=c)continue;
        //cerr<<dist[y][x]-c<<" "<<(dist[0][n-1]+dist[n-1][0])-ans<<"\n";
        auto p=v[x][y].find(c);
        if(p!=v[x][y].end())v[x][y].erase(v[x][y].find(c));
        v[y][x].insert(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(int j=0;j<n;j++){
                if(v[mini][j].size()){
                    curd[j]=min(
                        curd[j],
                        curd[mini]+*v[mini][j].begin()
                    );
                }
            }
        }
        /*
        for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        cerr<<"\n";
        */
        if(curd[n-1]==inf){
            v[y][x].erase(v[y][x].find(c));
            v[x][y].insert(c);
            continue;
        }
        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(int j=0;j<n;j++){
                if(v[mini][j].size()){
                    curd[j]=min(
                        curd[j],
                        curd[mini]+*v[mini][j].begin()
                    );
                }
            }
        }
        /*
        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";
        p=v[y][x].find(c);
        if(p!=v[y][x].end()){
            v[y][x].erase(v[y][x].find(c));
        }
        v[x][y].insert(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 9 ms 2652 KB Output is correct
2 Correct 24 ms 2652 KB Output is correct
3 Correct 118 ms 2900 KB Output is correct
4 Correct 133 ms 2652 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 29 ms 2660 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 47 ms 2568 KB Output is correct
11 Correct 56 ms 2652 KB Output is correct
12 Correct 53 ms 2648 KB Output is correct
13 Correct 116 ms 2652 KB Output is correct
14 Correct 112 ms 2700 KB Output is correct
15 Correct 88 ms 2648 KB Output is correct
16 Correct 131 ms 2700 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 489 ms 5936 KB Output is correct
2 Correct 579 ms 5968 KB Output is correct
3 Correct 237 ms 5716 KB Output is correct
4 Correct 71 ms 2780 KB Output is correct
5 Correct 100 ms 2720 KB Output is correct
6 Correct 60 ms 2652 KB Output is correct
7 Correct 44 ms 2664 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 1082 ms 7200 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2652 KB Output is correct
2 Correct 24 ms 2652 KB Output is correct
3 Correct 18 ms 5468 KB Output is correct
4 Correct 25 ms 2652 KB Output is correct
5 Correct 22 ms 5984 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1077 ms 5912 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 24 ms 2652 KB Output is correct
3 Correct 118 ms 2900 KB Output is correct
4 Correct 133 ms 2652 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 29 ms 2660 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 47 ms 2568 KB Output is correct
11 Correct 56 ms 2652 KB Output is correct
12 Correct 53 ms 2648 KB Output is correct
13 Correct 116 ms 2652 KB Output is correct
14 Correct 112 ms 2700 KB Output is correct
15 Correct 88 ms 2648 KB Output is correct
16 Correct 131 ms 2700 KB Output is correct
17 Correct 489 ms 5936 KB Output is correct
18 Correct 579 ms 5968 KB Output is correct
19 Correct 237 ms 5716 KB Output is correct
20 Correct 71 ms 2780 KB Output is correct
21 Correct 100 ms 2720 KB Output is correct
22 Correct 60 ms 2652 KB Output is correct
23 Correct 44 ms 2664 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Execution timed out 1082 ms 7200 KB Time limit exceeded
26 Halted 0 ms 0 KB -