Codeforces 301B Yaroslav and Time [최단로]

제목 링크: Codeforces 301B Yaroslav and Time
제목: n개점, 2~n-31 각 점에서 1회 스킬을 사용하여 a[i]를 회복할 수 있습니다.걷는 데 초당 시간 d가 걸리면 당신은 임의의 시간을 구매할 수 있습니다.언제든지 마이너스로 할 수 없도록 요구하며 1부터 n까지 최소한 구매할 시간이 필요하냐고 물어보세요.
사고방식: SB문제, d>=a[i].최단 누드 문제야...
AC 코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define fi first
#define se second
#define ll o<<1
#define rr o<<1|1
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 2*1e5 + 1;
const int pN = 1e6;// <= 10^7
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
void add(LL &x, LL y) { x += y; x %= MOD; }
int Map[110][110];
int a[110];
pii b[110];
int Dis(int i, int j) {
    return abs(b[i].fi - b[j].fi) + abs(b[i].se - b[j].se);
}
int main()
{
    int n, d; cin >> n >> d;
    for(int i = 2; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> b[i].fi >> b[i].se;
    }
    CLR(Map, INF);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) Map[i][j] = 0;
            else Map[i][j] = Dis(i, j) * d - a[j];
        }
    }
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);
            }
        }
    }
    cout << Map[1][n] << endl;
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS)

알고리즘 유형 : 다익스트라 or BFS 다익스트라 풀이 BFS 풀이 SOLVE 1) 풀이 요약 (다익스트라 풀이) 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다. 가중치가 모두 0 또는 양수이고, 특정...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다