oj.uz

답안 #964151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964151 2024-04-16T11:23:10 Z Akshat369 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 3720 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>=1e15){
        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 56 ms 344 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 68 ms 520 KB Output is correct
4 Correct 71 ms 348 KB Output is correct
5 Correct 25 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 12 ms 520 KB Output is correct
10 Correct 91 ms 520 KB Output is correct
11 Correct 94 ms 520 KB Output is correct
12 Correct 91 ms 344 KB Output is correct
13 Incorrect 48 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 520 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Execution timed out 1059 ms 2644 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 344 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 68 ms 520 KB Output is correct
4 Correct 71 ms 348 KB Output is correct
5 Correct 25 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 12 ms 520 KB Output is correct
10 Correct 91 ms 520 KB Output is correct
11 Correct 94 ms 520 KB Output is correct
12 Correct 91 ms 344 KB Output is correct
13 Incorrect 48 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -