oj.uz

답안 #7165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
7165 2014-07-27T12:53:11 Z baneling100 약속장소 정하기 (GCJ12KOR_appointment) C++
35 / 35
 880 ms 5832 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1524 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 880 ms 5832 KB Output is correct