oj.uz

Submission #220916

# Submission time Handle Problem Language Result Execution time Memory
220916 2020-04-09T09:15:00 Z Ruxandra985 Cities (BOI16_cities) C++14
22 / 100
 1620 ms 54348 KB 
#include <bits/stdc++.h>
#define DIMN 100010
#define INF 1000000000000000
using namespace std;
long long dist[64][DIMN];
int sp[DIMN] , poz[DIMN];
vector <pair <int,int> > v[DIMN];

priority_queue <pair <long long , pair <int,int> > > h;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , j , x , y , cost , nod , vecin , c , cst , mask , st;
    long long sum = 0;
    fscanf (fin,"%d%d%d",&n,&k,&m);

    for (i = 1 ; i <= k ; i++){
        fscanf (fin,"%d",&sp[i]);
        poz[sp[i]] = i;
    }

    for (i = 1 ; i <= m ; i++){
        fscanf (fin,"%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y , c));
        v[y].push_back(make_pair(x , c));
    }
    for (i = 0 ; i < 32 ; i++){
        for (j = 1 ; j <= n ; j++)
            dist[i][j] = INF;
    }

    for (j = 1 ; j <= n ; j++){
        if (poz[j]){
            dist[1 << (poz[j] - 1)][j] = 0;
            h.push(make_pair(0 , make_pair(1 << (poz[j] - 1) , j)));
        }
        else {
            dist[0][j] = 0;
            h.push(make_pair(0 , make_pair(0 , j)));
        }
    }


    while (!h.empty()){

        cost = -h.top().first;
        mask = h.top().second.first;
        nod = h.top().second.second;
        h.pop();

        if (dist[mask][nod] != cost)
            continue; /// nu e ok

        //printf ("%d %d %lld\n" , mask , nod , dist[mask][nod]);

        /// acuma trb sa vad cum se pot combina starile

        for (i = 0 ; i < v[nod].size() ; i++){
            vecin = v[nod][i].first;
            cst = v[nod][i].second;


            for (st = 0 ; st < 32 ; st++){
                if (mask & st)
                    continue;
                /// trb sa nu aiba niciun bit comun

                if (dist[mask | st][vecin] > dist[mask][nod] + cst + dist[st][vecin]){
                    dist[mask | st][vecin] = dist[mask][nod] + cst + dist[st][vecin];
                    h.push(make_pair(-dist[mask | st][vecin] , make_pair(mask|st , vecin)));
                }

            }


        }

    }

    sum = INF;

    for (i = 1 ; i <= n ; i++)
        sum = min(sum , dist[(1 << k) - 1][i]);

    fprintf (fout,"%lld",sum);

    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:59:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
cities.cpp:16:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&k,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:19:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&sp[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~
cities.cpp:24:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d%d",&x,&y,&c);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 36332 KB Output is correct
2 Correct 1620 ms 54348 KB Output is correct
3 Incorrect 213 ms 35184 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3840 KB Output is correct
2 Correct 14 ms 3968 KB Output is correct
3 Incorrect 8 ms 3200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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