Rezultati

Up. imeNalogaJezikRezultatČas oddaje
Aquasonic-2018 Avtocesta C++ 0/100Napačen odgovor (WA) 04. okt '18 @ 18:35

Test Točke Porabljen spomin Porabljen čas Status
#1 4/4 3,145 MiB 0,010 s OK
#2 4/4 3,109 MiB 0,010 s OK
#3 4/4 3,207 MiB 0,004 s OK
#4 4/4 3,059 MiB 0,000 s OK
#5 4/4 3,059 MiB 0,004 s OK
#6 0/4 3,055 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​16155
<<<EOF>>>
Pravilen izhod:
​15154
<<<EOF>>>
#7 4/4 3,059 MiB 0,004 s OK
#8 0/4 3,207 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​37468
<<<EOF>>>
Pravilen izhod:
​37168
<<<EOF>>>
#9 4/4 3,211 MiB 0,010 s OK
#10 4/4 3,066 MiB 0,004 s OK
#11 0/4 3,215 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​17491
<<<EOF>>>
Pravilen izhod:
​16823
<<<EOF>>>
#12 0/4 3,063 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​13935
<<<EOF>>>
Pravilen izhod:
​13712
<<<EOF>>>
#13 4/4 3,215 MiB 0,000 s OK
#14 0/4 3,063 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​21386
<<<EOF>>>
Pravilen izhod:
​20095
<<<EOF>>>
#15 4/4 3,070 MiB 0,004 s OK
#16 5/5 3,105 MiB 0,010 s OK
#17 5/5 3,199 MiB 0,000 s OK
#18 5/5 3,203 MiB 0,004 s OK
#19 5/5 3,059 MiB 0,004 s OK
#20 5/5 3,137 MiB 0,004 s OK
#21 0/5 3,105 MiB 0,035 s Napačen odgovor
Tvoj izhod:
​192179
<<<EOF>>>
Pravilen izhod:
​179087
<<<EOF>>>
#22 0/5 3,258 MiB 0,022 s Napačen odgovor
Tvoj izhod:
​203373
<<<EOF>>>
Pravilen izhod:
​202000
<<<EOF>>>
#23 0/5 3,105 MiB 0,028 s Napačen odgovor
Tvoj izhod:
​24316
<<<EOF>>>
Pravilen izhod:
​21816
<<<EOF>>>

Ocenjevani program (mainw.cpp):
#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
#define INF (1 << 27)
#define INFLL (1LL << 51)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;

const int maxn = 3 * 17;

int N, M, Q;
int ans = INF;
vector<pii> order, graph[maxn], ngraph[maxn];

int DP[maxn];
int parent[maxn];

void dijkstra(int S, int T)
{
    memset(parent, 0, sizeof parent);
    memset(DP, 0x2F, sizeof DP);
    DP[S] = 0;

    priority_queue<piii, vector<piii>, greater<piii> > pq;
    pq.push({DP[S], {S, S}});

    while (!pq.empty()) {
        int dist = pq.top().f, u = pq.top().s.f, prev = pq.top().s.s; pq.pop();
        if (DP[u] != dist) continue;

        parent[u] = prev;
        for (auto v : ngraph[u])
            if (DP[u] + v.s < DP[v.f]) {
                DP[v.f] = DP[u] + v.s;
                pq.push({DP[v.f], {v.f, u}});
            }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y, z; cin >> x >> y >> z;
        graph[x].push_back({y, z});
        graph[y].push_back({x, z});
    }

    cin >> Q;
    while (Q--) {
        int x, y; cin >> x >> y;
        order.push_back({x, y});
    }
    
    do
    {
        int cur = 0;
        
        for (int i = 1; i <= N; i++) ngraph[i].clear();
        for (int i = 1; i <= N; i++)
            for (auto u : graph[i])
                ngraph[i].push_back({u.f, u.s}); 
        
        
        for (int i = 0; i < order.size(); i++) {
            dijkstra(order[i].f, order[i].s);
            
            if (DP[order[i].s] >= 0x2F2F2F2F) assert(false);
            cur += DP[order[i].s];
            
            vector<pii> rem;
            int u = order[i].s;
            while (parent[u] != u) rem.push_back({parent[u], u}), u = parent[u];

            for (auto x : rem) {
                int u = x.f, v = x.s;

                for (auto &w : ngraph[u])
                    if (w.f == v) w.s = 0;
                
                for (auto &w : ngraph[v])
                    if (w.f == u) w.s = 0;
            }
        }
        
        ans = min(ans, cur);
    /// for (auto x : order) cout << x.f << " " << x.f << " | "; cout << endl;
    } while (next_permutation(order.begin(), order.end()));

    cout << ans << endl;
    return 0;
}