VM 10 Bài 12 - Tăng tốc mạng máy tính

Points: 0.26 (partial)

Time limit: 0.38s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

VM10 - Tác giả: Cosmin Gheorghe

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho mạng máy tính gồm ~N~ máy và ~M~ liên kết hai chiều giữa các máy. Các máy được đánh số từ ~1~ đến ~N~. Máy của Bờm là máy ~1~ còn máy của Cuội là máy ~N~. Mỗi đường nối cần tốn một giá trị thời gian khác nhau để dữ liệu truyền qua. Tốc độ kết nối giữa hai máy là độ dài đường truyền dữ liệu ngắn nhất giữa hai máy đó.

Tốc độ kết nối của mạng khá chậm khiến Bờm và Cuội không thể chơi Dota được, do đó Bờm quyết định mua ~K~ thiết bị tăng tốc mạng. Thiết bị tăng tốc mạng được gắn vào các đường truyền dữ liệu giữa hai máy. Mỗi thiết bị sẽ làm giảm thời gian truyền dữ liệu của đường truyền đi một nửa.

Hãy giúp Bờm đặt các thiết bị tăng tốc sao cho tốc độ kết nối giữa máy của Bờm và Cuội là nhanh nhất có thể để hai bạn có thể chơi Dota mà không bị lag!

Input

Dòng đầu chứa ~3~ số ~N~, ~M~, ~K~.

~M~ dòng tiếp theo, mỗi dòng chứa ~3~ số ~x~, ~y~, ~c~ mô tả một đường truyền dữ liệu: ~x~, ~y~ là số hiệu của hai máy tính, còn ~c~ là thời gian truyền dữ liệu.

~1 \le N \le 1000~
~1 \le M \le 10^{5}~
~1 \le K \le 10~
~1 \le c \le 10^{6}~

Output

In ra 1 số duy nhất là tốc độ kết nối nhanh nhất có thể sau khi đã lắp đặt các thiết bị tăng tốc, làm tròn đến 2 chữ số thập phân.

Sample Input

Sample Output

4.25

Note

Bờm lắp cả 2 thiết bị tăng tốc lên đường nối giữa máy 2 và máy 3.

Comments

Please read the guidelines before commenting.

-8
nguyenthihai14121980 commented on Aug. 4, 2024, 1:15 a.m.
gợi ý

.

include <bits/stdc++.h>

using namespace std;

typedef long long ll; typedef pair<int,int> ii; typedef unsigned long long ull;

define X first

define Y second

define pb push_back

define mp make_pair

define ep emplace_back

define EL printf("\n")

define sz(A) (int) A.size()

define FOR(i,l,r) for (int i=l;i<=r;i++)

define FOD(i,r,l) for (int i=r;i>=l;i--)

define fillchar(a,x) memset(a, x, sizeof (a))

define faster iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 1001, K = 11; const double inf = double(1e9+9.0); int n, m, k; double d[N][K]; vector<ii> a[N];

struct data { int u, j; double c; bool operator < (const data &o) const { return c > o.c; } };

void dijkstra() { FOR(i,1,n) FOR(j,0,k) d[i][j] = inf; d[1][0] = double(0.0); priority_queue<data> st; st.push({1, 0, d[1][0]}); while (! st.empty()) { data t = st.top(); st.pop(); int u = t.u, j = t.j; double c = t.c; if (c > d[u][j]) continue; for (auto e : a[u]) { int v = e.X; double w = (double) e.Y; FOR(i,j,k) { if (d[v][i] > d[u][j] + w) { d[v][i] = d[u][j] + w; st.push({v, i, d[v][i]}); } w /= 2.0; } } } }

int main() { // freopen("INP.TXT", "r", stdin); // freopen("OUT.TXT", "w", stdout);

scanf("%d%d%d", &n,&m,&k); while (m--) { int u, v, c; scanf("%d%d%d", &u,&v,&c); a[u].pb({v,c}); a[v].pb({u,c}); } dijkstra(); printf("%.2f\n", d[n][k]); return 0;

}
This comment is hidden due to too much negative feedback. Show it anyway.