백준 32899 (C++) Kruidnoten

최초 업로드: 2025-11-13 02:21:38

최근 수정 시간: 2025-11-13 02:21:55

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] Kruidnoten

[문제 링크](https://www.acmicpc.net/problem/32899)

## 문제 설명

Every week, Karlijn and her teammates join the competitive programming training at their university. Thinking and coding for such a long time is quite exhausting, and they need a ton of snacks to get through training. They have divided the chore of bringing snacks neatly: while the other two bring stroopwafels and salt sticks, Karlijn's duty is to provide kruidnoten.

She usually gets them on the way from home to university just before training. The bicycle network in her home town consists of intersections which are connected by cycleways of different lengths. The intersections are numbered from $1$ to $n$. Karlijn's house is at intersection $1$, and her university is at intersection $n$.

There are multiple stores that sell kruidnoten, but some of them are often out of stock. Karlijn wants to get to university as quickly as possible, so she has a habit of looking up online which stores still have kruidnoten before leaving her house. Using this information, she then takes the shortest path via some stocked store. An example is visualized in Figure K.1.

Figure K.1: A possible situation from Sample Input 1, where not every store is stocked with kruidnoten. In this case, Karlijn buys the kruidnoten at the store at intersection $3$, and the shortest path has length $11$.

Now, she wonders how much time she should usually plan for her way to training. From long-time experience, Karlijn knows for each store how likely it is that they have not sold out. In particular, she observed that the stock of kruidnoten is independent for each store. What is the expected length of a shortest path from Karlijn's house to university if she wants to visit some store that has kruidnoten in stock?

## 입력

The input consists of:

<ul>
	<li>One line with three integers $n$, $m$, and $k$ ($2\leq n\leq 2 \cdot 10^5$, $1\leq m\leq 2 \cdot 10^5$, $1\leq k\leq n$), the number of intersections, cycleways, and stores that may sell kruidnoten.</li>
	<li>$m$ lines, each with three integers $i$, $j$, and $\ell$ ($1\leq i, j\leq n$, $i \neq j$, $1 \leq \ell \leq 10^6$), indicating that the intersections $i$ and $j$ are connected by a cycleway of length $\ell$. It is guaranteed that every pair of intersections is connected by at most one cycleway. Further, it is possible to get from every intersection to every other intersection by bike.</li>
	<li>$k$ lines, each with one integer $i$ ($1\leq i \leq n$) and one floating-point number $p$ ($0 < p \leq 1$ with at most four digits after the decimal point), indicating that there is a store located at intersection $i$, and that the probability that it still has kruidnoten is $p$. It is guaranteed that there is at most one kruidnoten store at each intersection.</li>
</ul>

## 출력

If the event that Karlijn cannot get any kruidnoten on her way has probability $> 0$, output "<code>impossible</code>". Otherwise, output the expected length of a shortest path from her home to university if she gets kruidnoten on the way.

Your answer should have an absolute or relative error of at most $10^{-6}$.

## 풀이
- 확률이 1인 상점이 존재하지 않으면 "impossible"
- 시작점부터 다익스트라 1번, 끝점부터 다익스트라 1번을 통해 특정 상점을 통과하는 최단 거리 계산.
- 최단 거리가 작은 순서대로 확률을 보며, 해당 상점을 지나면서 이전 상점들에 모두 존재하지 않을 확률 * 해당 상점에 존재할 확률 * 해당 상점에서의 최단 거리의 합 계산

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

typedef long long ll;
typedef long double ld;
const int MAX = 200'001;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

vector<vector<pair<int, int>>> conn(MAX);
vector<ll> distFromStart(MAX, LINF);
vector<ll> distFromEnd(MAX, LINF);

struct element {
 int cur;
 ll cost;
 bool operator<(const element e) const {
 return cost > e.cost;
 }
};

void dijkstra(vector<ll> &minCost, int start) {
 priority_queue<element> pq; pq.push({start, 0});
 while(!pq.empty()) {
 auto [cur, cost] = pq.top(); pq.pop();
 if(cost>=minCost[cur]) continue;
 minCost[cur] = cost;
 for(auto [next, nextCost]:conn[cur]) {
 if(cost+nextCost<minCost[next]) pq.push({next, cost+nextCost});
 }
 }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    while(m--) {
        int i, j, l; cin >> i >> j >> l;
        conn[i].push_back({j, l});
        conn[j].push_back({i, l});
    }

vector<pair<int, ld>> store(k);
 for(int i=0;i<k;i++) cin >> store[i].first >> store[i].second;

dijkstra(distFromStart, 1);
 dijkstra(distFromEnd, n);
 sort(store.begin(), store.end(), [](pair<int, double> a, pair<int, double> b){
 return distFromStart[a.first]+distFromEnd[a.first] < distFromStart[b.first]+distFromEnd[b.first];
 });

bool prob1=false;
 ld res=0, total=1;
 for(auto [u, prob]:store) {
 ll dist = distFromStart[u]+distFromEnd[u];
 if(dist<=LINF) res += dist*(total*prob);
 total *= 1-prob;
 if(prob==1) prob1=true;
 }
 if(prob1) cout << setprecision(10) << fixed << res;
 else cout << "impossible";
}
```