글 읽기 - 반례가 있는지 모르겠습니다

jonghyeok613 6년 전 0

혹시 데이터에 자기 자신으로 가는 도로가 존재하나요?

아니면 다른 특정한 케이스가 있는 건가요

많이 틀리는 케이스를 알려 주시면 감사하겠습니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector< pair<int, int> > graph[2502];
int n, dis[2502][2502], inf = 10000000;
pair<int, int> cost[2502];
long long dp[2502], llinf = 2000000000;
priority_queue< pair<int, int> > heap;

void dijk(int st)
{
    int i, now, next, l, val;
    dis[st][st] = 0;
    heap.push(make_pair(0, st));
    while(heap.empty() == false){
        val = - heap.top().first;
        now = heap.top().second;
        heap.pop();
        if(dis[st][now] < val) continue;
        for(i=0; i<graph[now].size(); i++){
            next = graph[now][i].first;
            l = graph[now][i].second;
            if(dis[st][next] > dis[st][now] + l){
                dis[st][next] = dis[st][now] + l;
                heap.push(make_pair( - dis[st][next], next ));
            }
        }
    }
}

int main()
{
    int m, i, j, a, b, len;
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a);
        cost[i] = make_pair(a, i);
    }
    for(i=0; i<m; i++){
        scanf("%d %d %d", &a, &b, &len);
        graph[a].push_back(make_pair(b, len));
        graph[b].push_back(make_pair(a, len));
    }

    for(i=1; i<=n; i++){
        dp[i] = llinf;
        for(j=1; j<=n; j++)
            dis[i][j] = inf;
    }

    for(i=1; i<=n; i++) dijk(i);

    sort(cost + 2, cost + n);

    for(i=1; i<n/2; i++)
        swap(cost[1 + i], cost[n - i]);

    dp[1] = 0;

    for(i=1; i<n; i++){
        int now = cost[i].second;
        for(j=1; j<=n; j++)
           dp[j] = min(dp[j], dp[now] + (long long) cost[i].first * dis[now][j]);
    }

    printf("%I64d", dp[n]);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 있는지 모르겠습니다

jonghyeok613 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말