oj.uz

답안 #14718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
14718 2015-06-13T09:16:00 Z gs14004 약속장소 정하기 (GCJ12KOR_appointment) C++14
10 / 35
 3000 ms 12180 KB 
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;

vector<int> candidate[10005];
vector<pi> graph[10005];

int n, p, m;
int st[105], vel[105];
bool vis[10005];

void solve(){
    scanf("%d %d %d",&n,&p,&m);
    for (int i=1; i<=n; i++) {
        graph[i].clear();
        candidate[i].clear();
    }
    for (int i=1; i<=p; i++) {
        scanf("%d %d",&st[i],&vel[i]);
    }
    for (int i=0; i<m; i++) {
        int d, t, s;
        scanf("%d %d %d",&d,&t,&s);
        for (int j=1; j<t; j++) {
            int u;
            scanf("%d",&u);
            graph[s].push_back(pi(d,u));
            graph[u].push_back(pi(d,s));
            s = u;
        }
    }
    priority_queue<pi,vector<pi>,greater<pi> > pq;
    for (int i=1; i<=p; i++) {
        memset(vis,0,sizeof(vis));
        pq.push(pi(0,st[i]));
        while (!pq.empty()) {
            pi t = pq.top();
            pq.pop();
            if(vis[t.second]) continue;
            vis[t.second] = 1;
            candidate[t.second].push_back(t.first * vel[i]);
            for (auto &j : graph[t.second]){
                if(vis[j.second]) continue;
                pq.push(pi(j.first + t.first,j.second));
            }
        }
    }
    int pos = -1, posv = 1e9;
    for (int i=1; i<=n; i++) {
        if(candidate[i].size() != p) continue;
        int mv = *max_element(candidate[i].begin(),candidate[i].end());
        if(posv > mv) {
            posv = mv;
            pos = i;
        }
    }
    if(pos == -1) posv = -1;
    printf("%d",posv);
}

int main(){
    int t;
    scanf("%d",&t);
    for (int i=1; i<=t; i++) {
        printf("Case #%d: ",i);
        solve();
        puts("");
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3000 ms 12180 KB Program timed out