oj.uz

답안 #924377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924377 2024-02-09T02:11:35 Z yeediot Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 4368 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
struct edge{
    int a,b,c,d;
};
const int mxn=205;
vector<edge>e;
vector<pii>adj[mxn];
int dij(int st,int ed){
    vector<int>dis(mxn);
    for(int i=0;i<mxn;i++)dis[i]=2e18;
    dis[st]=0;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    pq.push({0,st});
    while(sz(pq)){
        auto [d,v]=pq.top();
        pq.pop();
        if(dis[v]<d)continue;
        for(auto [u,dd]:adj[v]){
            if(dis[v]+dd<dis[u]){
                dis[u]=dis[v]+dd;
                pq.push({dis[u],u});
            }
        }
    }
    return dis[ed];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        e.pb({a,b,c,d});
        adj[a].pb({b,c});
    }
    int ans=dij(1,n)+dij(n,1);
    for(int i=0;i<m;i++){
        for(int j=1;j<=n;j++){
            adj[j].clear();
        }
        for(int j=0;j<m;j++){
            if(j==i)continue;
            auto [a,b,c,d]=e[j];
            adj[a].pb({b,c});
        }
        adj[e[i].b].pb({e[i].a,e[i].c});
        int temp=e[i].d;
        temp+=dij(1,n)+dij(n,1);
        ans=min(ans,temp);
    }
    if(ans>(int)1e18){
        cout<<-1<<'\n';
        return 0;
    }
    cout<<ans<<'\n';
}
/*
*/

Compilation message

ho_t4.cpp: In function 'long long int dij(long long int, long long int)':
ho_t4.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         auto [d,v]=pq.top();
      |              ^
ho_t4.cpp:33:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         for(auto [u,dd]:adj[v]){
      |                  ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |             auto [a,b,c,d]=e[j];
      |                  ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 532 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 39 ms 492 KB Output is correct
4 Correct 46 ms 728 KB Output is correct
5 Correct 16 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 10 ms 348 KB Output is correct
10 Correct 61 ms 532 KB Output is correct
11 Correct 61 ms 344 KB Output is correct
12 Correct 62 ms 348 KB Output is correct
13 Correct 23 ms 348 KB Output is correct
14 Correct 26 ms 348 KB Output is correct
15 Correct 24 ms 556 KB Output is correct
16 Correct 27 ms 600 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1071 ms 3428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 524 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Execution timed out 1022 ms 4368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 532 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 39 ms 492 KB Output is correct
4 Correct 46 ms 728 KB Output is correct
5 Correct 16 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 10 ms 348 KB Output is correct
10 Correct 61 ms 532 KB Output is correct
11 Correct 61 ms 344 KB Output is correct
12 Correct 62 ms 348 KB Output is correct
13 Correct 23 ms 348 KB Output is correct
14 Correct 26 ms 348 KB Output is correct
15 Correct 24 ms 556 KB Output is correct
16 Correct 27 ms 600 KB Output is correct
17 Execution timed out 1071 ms 3428 KB Time limit exceeded
18 Halted 0 ms 0 KB -