oj.uz

Submission #649612

# Submission time Handle Problem Language Result Execution time Memory
649612 2022-10-11T03:59:46 Z Khoa Ceste (COCI17_ceste) C++14
160 / 160
 117 ms 6856 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;
typedef array<ll, 3> iii;

void print() { cerr << '\n'; } template <typename T1, typename... T2>
void print(const T1 &a, const T2 &...args) { cerr << a << ' ', print(args...); }

const int N = 2e3 + 5;
const int mod = 1e9 + 7;

int a[N], n, m;
ll costb[N], res[N];
vector<iii> g[N];

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        g[u].pb({v, a, b});
        g[v].pb({u, a, b});
    }
    for(int i = 1; i <= n; i++) costb[i] = res[i] = 1e17;
    
    priority_queue<iii, vector<iii>, greater<iii>> q;
    q.push({0, 0, 1});
    res[1] = 0;
    
    while(q.size())
    {
        ll u = q.top()[2], a = q.top()[0], b = q.top()[1];
        q.pop();
        if(costb[u] <= b) continue;
        costb[u] = b;
        res[u] = min(res[u], a * b);
        
        for(iii &v : g[u]) if(b + v[2] < costb[v[0]])
            q.push({a + v[1], b + v[2], v[0]});
    }
    for(int i = 2; i <= n; i++) cout << (res[i] == 1e17 ? -1 : res[i]) << '\n';
    
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 620 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1232 KB Output is correct
2 Correct 11 ms 1312 KB Output is correct
3 Correct 11 ms 1492 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2124 KB Output is correct
2 Correct 117 ms 6856 KB Output is correct
3 Correct 2 ms 724 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 792 KB Output is correct
2 Correct 102 ms 3800 KB Output is correct
3 Correct 5 ms 596 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1056 KB Output is correct
2 Correct 106 ms 2200 KB Output is correct
3 Correct 90 ms 2252 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 2176 KB Output is correct
2 Correct 90 ms 2248 KB Output is correct
3 Correct 116 ms 2208 KB Output is correct