oj.uz

Submission #964123

# Submission time Handle Problem Language Result Execution time Memory
964123 2024-04-16T10:47:56 Z Akshat369 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 3712 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;
     
        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>=(int)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 53 ms 600 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 77 ms 524 KB Output is correct
4 Correct 73 ms 520 KB Output is correct
5 Correct 33 ms 544 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 13 ms 348 KB Output is correct
10 Correct 96 ms 520 KB Output is correct
11 Correct 91 ms 344 KB Output is correct
12 Correct 93 ms 520 KB Output is correct
13 Incorrect 64 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 1067 ms 3712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 516 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Execution timed out 1096 ms 2676 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 600 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 77 ms 524 KB Output is correct
4 Correct 73 ms 520 KB Output is correct
5 Correct 33 ms 544 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 412 KB Output is correct
9 Correct 13 ms 348 KB Output is correct
10 Correct 96 ms 520 KB Output is correct
11 Correct 91 ms 344 KB Output is correct
12 Correct 93 ms 520 KB Output is correct
13 Incorrect 64 ms 512 KB Output isn't correct
14 Halted 0 ms 0 KB -