oj.uz

답안 #964121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964121 2024-04-16T10:46:14 Z Akshat369 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 4448 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>=(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

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 103 ms 540 KB Output is correct
4 Correct 72 ms 544 KB Output is correct
5 Correct 24 ms 560 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 11 ms 548 KB Output is correct
10 Correct 95 ms 544 KB Output is correct
11 Correct 88 ms 564 KB Output is correct
12 Correct 93 ms 344 KB Output is correct
13 Incorrect 54 ms 532 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 103 ms 540 KB Output is correct
4 Correct 72 ms 544 KB Output is correct
5 Correct 24 ms 560 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 11 ms 548 KB Output is correct
10 Correct 95 ms 544 KB Output is correct
11 Correct 88 ms 564 KB Output is correct
12 Correct 93 ms 344 KB Output is correct
13 Incorrect 54 ms 532 KB Output isn't correct
14 Halted 0 ms 0 KB -