oj.uz

답안 #964150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964150 2024-04-16T11:19:51 Z Akshat369 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 4568 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]);
    }
    vector<pii> adj[n+1];
    for(int j = 0 ; j < m ; j++){
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 532 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 80 ms 472 KB Output is correct
4 Correct 77 ms 544 KB Output is correct
5 Correct 26 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 14 ms 344 KB Output is correct
10 Correct 92 ms 544 KB Output is correct
11 Correct 88 ms 560 KB Output is correct
12 Correct 92 ms 600 KB Output is correct
13 Incorrect 63 ms 532 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 536 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Execution timed out 1079 ms 3388 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 532 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 80 ms 472 KB Output is correct
4 Correct 77 ms 544 KB Output is correct
5 Correct 26 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 14 ms 344 KB Output is correct
10 Correct 92 ms 544 KB Output is correct
11 Correct 88 ms 560 KB Output is correct
12 Correct 92 ms 600 KB Output is correct
13 Incorrect 63 ms 532 KB Output isn't correct
14 Halted 0 ms 0 KB -