Submission #2647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2647	2013-07-30T06:26:27 Z	tncks0121	약속장소 정하기 (GCJ12KOR_appointment)	C++	35 / 35	712 ms	6316 KB

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <memory.h>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;

const int N_ = 10005;
const int P_ = 105;
const int M_ = 1005;

struct Edge {
    int u, c;
    Edge(int u = 0, int c = 0): u(u), c(c) { }
    bool operator< (const Edge &t) const { return c > t.c; }
};

int TC, TCC;

int N, P, M;
int X[P_], V[P_];
vector<Edge> Gph[N_];

int dist[N_];
bool visited[N_];
priority_queue<Edge> PQ;
bool cannot[N_];
int result[N_];

int main() {
    int i, j;

    scanf("%d\n", &TC);
    while(++TCC <= TC) {
        scanf("%d%d%d", &N, &P, &M);
        for(i = 1; i <= N; i++) Gph[i].clear();

        for(i = 1; i <= P; i++) scanf("%d%d", X+i, V+i);

        while(M--) {
            int d, l, s; scanf("%d%d%d", &d, &l, &s);
            while(--l) {
                int t; scanf("%d", &t);
                Gph[s].push_back( Edge(t, d) );
                Gph[t].push_back( Edge(s, d) );
                s = t;
            }
        }


        for(i = 1; i <= N; i++) cannot[i] = false, result[i] = 0;

        for(int w = 1; w <= P; w++) {
            int u = X[w];

            for(i = 1; i <= N; i++) dist[i] = 2147483647, visited[i] = 0;
            while(!PQ.empty()) PQ.pop();

            PQ.push ( Edge(u, 0) );
            dist[u] = 0;

            while(!PQ.empty()) {
                Edge t = PQ.top(); PQ.pop();
                if(visited[t.u]) continue;
                visited[t.u] = true;
                for(i = 0; i < Gph[t.u].size(); i++) {
                    Edge &e = Gph[t.u][i];
                    if(!visited[e.u] && dist[e.u] > t.c + e.c) {
                        dist[e.u] = t.c + e.c;
                        PQ.push (Edge(e.u, t.c + e.c));
                    }
                }
            }

            int val = 0;
            for(i = 1; i <= N; i++) {
                if(!visited[i]) cannot[i] = true;
                else result[i] = max(result[i], dist[i] * V[w]);
            }
        }

        int res = 2147483647;
        bool stored = false;

        for(i = 1; i <= N; i++) {
            if(!cannot[i]) stored = true, res = min(res, result[i]);
        }

        printf("Case #%d: %d\n", TCC, stored ? res : -1);
    }

    return 0;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

25.0 / 25.0

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