oj.uz

Submission #649609

# Submission time Handle Problem Language Result Execution time Memory
649609 2022-10-11T03:41:51 Z Khoa Ceste (COCI17_ceste) C++14
0 / 160
 3 ms 596 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] = costb[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;
        res[u] = min(res[u], a * b);
        
        for(iii &v : g[u]) if(b + v[2] < costb[v[0]])
        {
            costb[v[0]] = b + v[2];
            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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -