oj.uz

Submission #535716

# Submission time Handle Problem Language Result Execution time Memory
535716 2022-03-11T02:33:24 Z sam571128 Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 4272 KB 
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 205;

struct edge{
    int u,v,w,x;
};

vector<edge> edges;
vector<int> adj[N];
int dis[N];
int n,m;

int ans = 1e18;

void dijkstra(int tmp){
    int res = 0;
    fill(dis,dis+N,1e18);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    dis[1] = 0;
    pq.push({0,1});

    while(!pq.empty()){
        auto [ww,u] = pq.top(); pq.pop();
        if(ww > dis[u]) continue;
        for(auto eid : adj[u]){
            if(edges[eid].u==u){
                if(dis[edges[eid].v] > dis[u] + edges[eid].w){
                    dis[edges[eid].v] = dis[u] + edges[eid].w;
                    pq.push({dis[edges[eid].v],edges[eid].v});
                }
            }
        }
    }
    res += dis[n];

    fill(dis,dis+N,1e18);
    dis[n] = 0;
    pq.push({0,n});

    while(!pq.empty()){
        auto [ww,u] = pq.top(); pq.pop();
        if(ww > dis[u]) continue;
        for(auto eid : adj[u]){
            if(edges[eid].u==u){
                if(dis[edges[eid].v] > dis[u] + edges[eid].w){
                    dis[edges[eid].v] = dis[u] + edges[eid].w;
                    pq.push({dis[edges[eid].v],edges[eid].v});
                }
            }
        }
    }
    res += dis[1];
    ans = min(ans,res+tmp);
}

signed main(){
    fastio
    cin >> n >> m;

    for(int i = 0;i < m;i++){
        int u,v,c,d;
        cin >> u >> v >> c >> d;
        adj[u].push_back(edges.size());
        adj[v].push_back(edges.size());
        edges.push_back({u,v,c,d});
    }

    dijkstra(0);

    for(auto &e : edges){
        swap(e.u,e.v);
        dijkstra(e.x);
        swap(e.u,e.v);
    }

    cout << (ans==1e18 ? -1 : ans) << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 380 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 57 ms 340 KB Output is correct
4 Correct 63 ms 340 KB Output is correct
5 Correct 23 ms 396 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 6 ms 408 KB Output is correct
10 Correct 104 ms 380 KB Output is correct
11 Correct 86 ms 384 KB Output is correct
12 Correct 89 ms 384 KB Output is correct
13 Correct 31 ms 340 KB Output is correct
14 Correct 47 ms 340 KB Output is correct
15 Correct 33 ms 340 KB Output is correct
16 Correct 36 ms 340 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 4272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Execution timed out 1095 ms 3268 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 380 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 57 ms 340 KB Output is correct
4 Correct 63 ms 340 KB Output is correct
5 Correct 23 ms 396 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 6 ms 408 KB Output is correct
10 Correct 104 ms 380 KB Output is correct
11 Correct 86 ms 384 KB Output is correct
12 Correct 89 ms 384 KB Output is correct
13 Correct 31 ms 340 KB Output is correct
14 Correct 47 ms 340 KB Output is correct
15 Correct 33 ms 340 KB Output is correct
16 Correct 36 ms 340 KB Output is correct
17 Execution timed out 1078 ms 4272 KB Time limit exceeded
18 Halted 0 ms 0 KB -