CC

自然万物都趋向从有序变得无序

0%

LightOJ - 1321 Sending Packets (期望+最短路)

发表于 更新于 分类于 Valine：

题目链接

Problem Description

Alice and Bob are trying to communicate through the internet. Just assume that there are N routers in the internet and they are numbered from 0 to N-1. Alice is directly connected to router 0 and Bob is directly connected to router N-1. Alice initiates the connection and she wants to send S KB of data to Bob.

Data can go to the (N-1)th router from the 0th router either directly or via some intermediate routers. There are some bidirectional links between some routers.

The links between the routers are not necessarily 100% perfect. So, for each link, a probability pi is given. That means if u and v are two routers and if their underlying link has probability pi, it means that if data is sent from u to v, the probability of successfully getting the data in v is pi and vice versa. If multiple links are used the probability of getting the data in destination is the multiplication of the probabilities of the links that have been used.

Assume that it takes exactly K seconds for a packet to reach Bob’s router from Alice’s router (independent on the number of links) if it’s successful. And when the data is successfully received in Bob’s router, it immediately sends an acknowledgement to Alice’s router and the acknowledgement always reaches her router exactly in K seconds (it never disappears).

Alice’s router used the following algorithm for the data communication.

  1. At time 0, the first KB of data is chosen to be sent.

  2. It establishes a path (it takes no time) to the destination router and sends the data in this route.

  3. It waits for exactly 2K seconds.

    a. If it gets the acknowledgement of the current data in this interval

                       i.      If S KB of data are sent, then step 4 is followed.

                    ii.      Otherwise, it takes 1 KB of the next data, and then step 2 is followed.

    b. Otherwise it resends the current 1 KB of data and then step 2 is followed.

  4. All the data are sent, so it reports Alice.

Assume that the probabilities of the links are static and independent. That means it doesn’t depend on the result of the previously sent data. Now your task is to choose some routes through the routers such that data can be sent in these routes and the expected time to send all the data to the destination routes is minimized. You only have to report the minimum expected time.

Input

Input starts with an integer T (T≤ 100), denoting the number of test cases.

Each case starts with a line containing four integers N (2 ≤ N ≤ 100)**, M (1 ≤ M), **S (1 ≤ S ≤ 109) and K (1 ≤ K ≤ 20), where M denotes the number of bidirectional links. Each of the next M lines contains three integers ui vi pi, meaning that there is a link between router ui and vi the probability for a successful message transfer in this link is pi% (0 ≤ ui, vi < N, ui ≠ vi, 0 < pi ≤ 100). There will be at most one link between two routers.

Output

For each case, print the case number and the minimum possible expected time to send all the data. Errors less than 1e-3 will be ignored. You can assume that at least one valid route between them always exists. And the result will be less than 1e13.

Sample intput

2

5 5 1 10

0 1 70

0 2 40

2 3 100

1 3 50

4 3 80

2 1 30 2

0 1 80

Sample Output

Case 1: 62.5000000000

Case 2: 150

题意:

给定一张无向图，每条边都有一个通过的概率 ，如果无法通过，那么就要回到起点重新出发 从起点到终点的时间固定为K，如果成功到达，又需要额外花费K的时间，问走S次的最小期望时间.

思路:

我们知道这s次肯定的独立的，所以我们只需要求出每一次的期望即可，

对于每一次，我们假设成功走到终点的概率为p，设期望为E。

那么E = p × 2×k + (1 - p) ×(E + 2 × k)

化简得：E = 2×k/p;

那么对于每一次我们只需要求出从0到n-1的最大的概率即可，那么我们可以随便跑一跑最短路求出最概率即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*************************************************************************
    > File Name: LightOJ-1321.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月11日 星期六 08时40分50秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 1e4 + 10;

struct ss{
    int to, nx;
    double w;
}a[maxn];
int head[maxn];
double dis[maxn];
bool vis[maxn];
int k;

void add(int u, int v, double w){
    a[k].to = v;
    a[k].w = w;
    a[k].nx = head[u];
    head[u] = k++;
}

void init(){
    k = 0;
    for(int i = 0; i < maxn; ++i)
        head[i] = -1,vis[i] =dis[i] =  0;
}

void SPFA(int s){
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    dis[s] = 1;
    while(!q.empty()){
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for(int st = head[t]; st != -1; st = a[st].nx){
            int to = a[st].to;
            double w = a[st].w;
            if(dis[to] < dis[t] * w){
                dis[to] = dis[t] * w;
                if(!vis[to]){
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
}

int main(){
    int t, kase = 0;
    scanf("%d", &t);
    while(t--){
        init();
        int n,m,s,k;
        scanf("%d%d%d%d",&n,&m,&s,&k);
        while(m--){
            int u,v;
            double w;
            scanf("%d%d%lf", &u, &v, &w);
            w /= 100;
            add(u,v,w);
            add(v,u,w);
        }
        SPFA(0);
        double p = dis[n-1];
        double ans = 2.0*s*k/p;
        printf("Case %d: %f\n",++kase, ans);
    }
    return 0;
}