Submission #649612

#	Time	Username	Problem	Language	Result	Execution time	Memory
649612		Khoa	Ceste (COCI17_ceste)	C++14	160 / 160	117 ms	6856 KiB

ceste

#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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16