oj.uz

Submission #964118

# Submission time Handle Problem Language Result Execution time Memory
964118 2024-04-16T10:42:42 Z Akshat369 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 3680 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define INF (int)1e18
#define endl '\n'
const int mod = 1000 * 1000 * 1000 + 7;
const int N = 100005;
#define f first
#define s second
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define rrep(i, a, b) for(int i = (a); i > (b); i--)
#define vi vector<int>
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
  
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
/*
 
*/
 
struct node{
    int u , v , c , d;
};
 
vector<int> dij(int src, vector<pii> adj[], int n) {
    vector<int> dis(n, INF);
    vector<int> vis(n, false);
 
    dis[src] = 0;
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.push({0, src});
 
    while (!pq.empty()) {
        auto uu = pq.top();
        pq.pop();
        int u = uu.second;
        if (vis[u]) continue;
        vis[u] = true;
 
        for (auto& vv : adj[u]) {
            int v = vv.first;
            int weight = vv.second;
            if (dis[v] > dis[u] + weight) {
                dis[v] = dis[u] + weight;
                pq.push({dis[v], v});
            }
        }
    }
    return dis;
}
 
 
void Solve() {
    int n , m; cin>>n>>m;
    vector<node> edge(m);
    for (int i = 0; i < m ; ++i) {
        cin>>edge[i].u>>edge[i].v>>edge[i].c>>edge[i].d;
    }
    int ans = 1e18;
    for(int i = 0 ; i < m ; i++){
        vector<pii> adj[n+1];
        for(int j = 0 ; j < m ; j++){
            if (i==j){
                adj[edge[j].v].push_back({edge[j].u,edge[j].c+edge[j].d});
            }
            else  adj[edge[j].u].push_back({edge[j].v,edge[j].c});
        }
        vi dis1(n+1), dis2(n+1) ;
        dis1 = dij(1, adj, n+1);
        dis2 = dij(n, adj, n+1);
//        debug(i,dis1);
//        debug(i,dis2);
//        for (int j = 0; j < n + 1; ++j) {
//            debug(j,adj[j]);
//        }
        ans = min(ans, dis1[n] + dis2[1]);
    }
  	if(ans>=1e18){
      cout<<-1<<endl;
    }
  else   cout << ans << endl;
}
 
int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    int t = 1;
 //   cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 68 ms 348 KB Output is correct
4 Correct 72 ms 348 KB Output is correct
5 Correct 25 ms 512 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 0 ms 424 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 12 ms 344 KB Output is correct
10 Correct 92 ms 348 KB Output is correct
11 Correct 88 ms 344 KB Output is correct
12 Correct 101 ms 544 KB Output is correct
13 Incorrect 48 ms 512 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 520 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Execution timed out 1063 ms 3680 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 68 ms 348 KB Output is correct
4 Correct 72 ms 348 KB Output is correct
5 Correct 25 ms 512 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 0 ms 424 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 12 ms 344 KB Output is correct
10 Correct 92 ms 348 KB Output is correct
11 Correct 88 ms 344 KB Output is correct
12 Correct 101 ms 544 KB Output is correct
13 Incorrect 48 ms 512 KB Output isn't correct
14 Halted 0 ms 0 KB -