Submission #7165

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
7165	2014-07-27T12:53:11 Z	baneling100	약속장소 정하기 (GCJ12KOR_appointment)	C++	35 / 35	880 ms	5832 KB

C

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
vector <ppair> A[10001];
priority_queue <ppair,vector<ppair>,greater<ppair> > Q;
int T, N, P, M, X[101], V[101], D[10001], Ans[10001], Res, Y;

void input(void)
{
    int i, j, d, l, c1, c2;

    scanf("%d %d %d",&N,&P,&M);
    Res=INF;
    for(i=1 ; i<=N ; i++)
    {
        A[i].clear();
        Ans[i]=0;
    }
    for(i=1 ; i<=P ; i++)
        scanf("%d %d",&X[i],&V[i]);
    for(i=1 ; i<=M ; i++)
    {
        scanf("%d %d %d",&d,&l,&c1);
        for(j=2 ; j<=l ; j++)
        {
            scanf("%d",&c2);
            A[c1].push_back(make_pair(c2,d));
            A[c2].push_back(make_pair(c1,d));
            c1=c2;
        }
    }
}

void process(void)
{
    int i, j, k, now;

    for(i=1 ; i<=P ; i++)
    {
        for(j=1 ; j<=N ; j++)
            D[j]=INF;
        D[X[i]]=0;
        Q.push(make_pair(0,X[i]));
        while(!Q.empty())
        {
            now=Q.top().second;
            Q.pop();
            k=A[now].size();
            for(j=0 ; j<k ; j++)
                if(D[A[now][j].first]>D[now]+A[now][j].second)
                {
                    D[A[now][j].first]=D[now]+A[now][j].second;
                    Q.push(make_pair(D[A[now][j].first],A[now][j].first));
                }
        }
        for(j=1 ; j<=N ; j++)
        {
            if(D[j]!=INF)
                D[j]*=V[i];
            if(Ans[j]<D[j])
                Ans[j]=D[j];
        }
    }
    for(i=1 ; i<=N ; i++)
        if(Res>Ans[i])
            Res=Ans[i];
}

void output(void)
{
    if(Res==INF)
        printf("Case #%d: -1\n",Y);
    else
        printf("Case #%d: %d\n",Y,Res);
}

int main(void)
{
    int i;

    scanf("%d",&T);
    for(i=1 ; i<=T ; i++)
    {
        Y=i;
        input();
        process();
        output();
    }
    return 0;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	880 ms	5832 KB	Output is correct