oj.uz

답안 #705873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705873 2023-03-05T14:44:11 Z Gital Autobus (COCI22_autobus) C++11
30 / 70
 1000 ms 12352 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;

ll n,m,a,b,w;
ll k,q,c,d;
vector<pair<ll,ll>> v[72];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
ll dp[72][72][72];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> a >> b >> w;
        v[a].push_back({w,b});
    }
    cin >> k >> q;
    if(k > 70) k = 70;
    for(int i = 0; i < 71; i++) {
        for(int j = 0; j < 71; j++) {
            for(int l= 0; l < 71; l++) dp[i][j][l] = -1;
        }
    }
    for(int j = 1; j <= n; j++) {
        pq.push({0,j});
        for(int i = 0; i < 72; i++) dp[j][j][i] = 0;
        while(!pq.empty()) {
            a = pq.top().first;
            b = pq.top().second;
            pq.pop();
            for(int i = 0; i < v[b].size(); i++) {
                bool able = false;
                for(int l = a; l < k; l++) {
                    if(dp[j][b][l] != -1  && (dp[j][v[b][i].second][l + 1] == -1 || dp[j][v[b][i].second][l + 1] > dp[j][b][l] + v[b][i].first)) {
                        dp[j][v[b][i].second][l + 1] = dp[j][b][l] + v[b][i].first;
                        if(!able) pq.push({l + 1,v[b][i].second});
                        able = true;
                    }
                }

            }
        }
    }
    /*for(int i = 1; i < 5; i++) {
        cout << "i = " << i << endl;
        for(int j = 1; j < 5; j++) {
            cout << "j = " << j << endl;
            for(int l= 0; l < 2; l++)  {
                cout << dp[i][j][l] << ' ';
            }
            cout << endl;
        }
    }*/
    for(int i = 0; i < q; i++) {
        cin >> c >> d;
        cout << dp[c][d][k] << endl;
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for(int i = 0; i < v[b].size(); i++) {
      |                            ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3144 KB Output is correct
4 Correct 2 ms 3144 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3284 KB Output is correct
2 Correct 3 ms 3284 KB Output is correct
3 Correct 4 ms 3284 KB Output is correct
4 Correct 4 ms 3284 KB Output is correct
5 Correct 5 ms 3284 KB Output is correct
6 Correct 9 ms 3412 KB Output is correct
7 Correct 13 ms 3488 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3144 KB Output is correct
4 Correct 2 ms 3144 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 8 ms 3284 KB Output is correct
8 Correct 18 ms 3288 KB Output is correct
9 Correct 5 ms 3284 KB Output is correct
10 Correct 23 ms 3224 KB Output is correct
11 Correct 48 ms 3480 KB Output is correct
12 Correct 239 ms 3468 KB Output is correct
13 Execution timed out 1070 ms 12352 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3144 KB Output is correct
4 Correct 2 ms 3144 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 3 ms 3284 KB Output is correct
8 Correct 3 ms 3284 KB Output is correct
9 Correct 4 ms 3284 KB Output is correct
10 Correct 4 ms 3284 KB Output is correct
11 Correct 5 ms 3284 KB Output is correct
12 Correct 9 ms 3412 KB Output is correct
13 Correct 13 ms 3488 KB Output is correct
14 Correct 8 ms 3284 KB Output is correct
15 Correct 18 ms 3288 KB Output is correct
16 Correct 5 ms 3284 KB Output is correct
17 Correct 23 ms 3224 KB Output is correct
18 Correct 48 ms 3480 KB Output is correct
19 Correct 239 ms 3468 KB Output is correct
20 Execution timed out 1070 ms 12352 KB Time limit exceeded
21 Halted 0 ms 0 KB -