AtCoder Beginner Contest 422-F (C++) Eat and Ride

최초 업로드: 2025-09-07 07:30:17

최근 수정 시간: 2025-09-07 07:36:05

카테고리: Atcoder

# F - Eat and Ride
[문제 링크](https://atcoder.jp/contests/abc422/tasks/abc422_f)

## Problem Statement

There is a connected undirected graph with $N$ vertices and $M$ edges.  
The vertices are numbered $1,2,\ldots,N$, and the $i$-th edge $(1\le i\le M)$ connects vertices $u_i$ and $v_i$.

For $i = 1,2,\ldots,N$, solve the following problem:

- Initially, Takahashi's weight is $0$.
- He travels by car to visit vertex $1$ and moves toward vertex $i$.
- When he visits vertex $v (1\le v\le N)$, his weight increases by $W_v$.
- The car he is riding can move along the edges.  
  When he passes through an edge, letting $X$ be his weight at that time, the car consumes $X$ fuel.

Find the minimum amount of fuel consumed for him to reach vertex $i$.

## Constraints

- $1 \le N \le 5000$
- $1 \le M \le 5000$
- $1 \le W_i \le 10^{9}\ \ (1\le i\le N)$
- $1 \le u_i \le v_i \le N\ \ (1\le i\le M)$
- The given graph is connected.
- All input values are integers.

## Input

The input is given from Standard Input in the following format:

$N$ $M$  
$W\_1$ $W\_2$ $\ldots$ $W\_N$  
$u\_1$ $v\_1$  
$u\_2$ $v\_2$  
$\vdots$  
$u\_M$ $v\_M$

## Output

Output over $N$ lines.  
On the $i$-th line $(1 \le i \le N)$, output the amount of fuel needed for Takahashi to reach vertex $i$.

## 풀이
항상 최소가 되도록 경로를 따라가는 것이 어느 점에서는 최단 경로가 아닐 수 있기 때문에 현재 누적된 무게를 중심으로 다익스트라로 해결하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 5'000;

ll w[MAX], minFuel[MAX];
vector<vector<int>> conn(MAX);

struct pos {
    ll idx, cost, fuel;
    bool operator<(const pos p) const {
        if(cost!=p.cost) return cost > p.cost;
        return fuel > p.fuel;
    }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i=0;i<n;i++) cin >> w[i];
    while(m--) {
        int u, v; cin >> u >> v;
        conn[u-1].push_back(v-1);
        conn[v-1].push_back(u-1);
    }

fill(minFuel, minFuel+n, LONG_LONG_MAX);
    priority_queue<pos> pq; pq.push({0, w[0], 0});
    minFuel[0]=0;
    while(!pq.empty()) {
        pos cur = pq.top(); pq.pop();
        for(int next:conn[cur.idx]) {
            pos n = {next, cur.cost+w[next], cur.cost+cur.fuel};
            if(minFuel[next]>n.fuel) {
                minFuel[next] = n.fuel;
                pq.push(n);
            }
        }
    }
    for(int i=0;i<n;i++) cout << minFuel[i] << '\n';
}
```